双向链接列表-合并排序后更新列表->尾]] << [

Question

在双向链表的实现中，我使用的是典型结构：

struct node
{
    void *data;
    struct node *prev;
    struct node *next;
};

我还将在O（1）时间插入列表的末尾，因此我还有另一个struct存储了head和tail：

struct linklist
{
    struct node *head;
    struct node *tail;
    size_t size;
};

程序对于所有插入和删除操作均按预期方式工作，但是排序功能存在问题，我使用的是归并排序算法，因为我知道它是对列表进行排序最有效或最有效的方法之一，该算法效果很好：

static struct node *split(struct node *head)
{
    struct node *fast = head;
    struct node *slow = head;

    while ((fast->next != NULL) && (fast->next->next != NULL))
    {
        fast = fast->next->next;
        slow = slow->next;
    }

    struct node *temp = slow->next;

    slow->next = NULL;
    return temp;
}

static struct node *merge(struct node *first, struct node *second, int (*comp)(const void *, const void *))
{
    if (first == NULL)
    {
        return second;
    }
    if (second == NULL)
    {
        return first;
    }
    if (comp(first->data, second->data) < 0)
    {
        first->next = merge(first->next, second, comp);
        first->next->prev = first;
        first->prev = NULL;
        return first;
    }
    else
    {
        second->next = merge(first, second->next, comp);
        second->next->prev = second;
        second->prev = NULL;
        return second;
    }
}

static struct node *merge_sort(struct node *head, int (*comp)(const void *, const void *))
{
    if ((head == NULL) || (head->next == NULL))
    {
        return head;
    }

    struct node *second = split(head);

    head = merge_sort(head, comp);
    second = merge_sort(second, comp);
    return merge(head, second, comp);
}

但是我不知道如何更新list->tail的地址：

void linklist_sort(struct linklist *list, int (*comp)(const void *, const void *))
{
    list->head = merge_sort(list->head, comp);
    // list->tail is no longer valid at this point
}

确定我可以在订购后遍历整个列表，并通过蛮力更新list->tail，但我想知道是否有更完美的方法。

我设法使用循环列表解决了问题，但我想避免更改程序的结构。

在双向链表的实现中，我使用的是典型结构：struct node {void * data;结构节点*上一页; struct节点* next; };我还将在...的末尾插入...

Answer 1

您的算法通过对每个步骤递归merge函数来使用O（N）堆栈空间。使用这种方法，跟踪tail节点将非常麻烦。您只需扫描列表即可找到并更新list中的linklist_sort结构。这个额外的步骤不会改变分类操作的复杂性。您可以通过从link->tail的当前值开始节省一些时间：如果列表已经排序，循环将立即停止。

Answer 2

[一种选择是将排序的节点视为单个列表节点，然后对其进行排序，然后设置一次以设置先前的指针，并更新尾指针。

Answer 3

我不是提供有关算法

Big-O