c - C中的链表合并排序实现中丢失的节点

Question

此实现用于按字母升序对字符串进行排序。我已经包含了负责划分节点的函数。 head 是链表的头部。

我相信 mergeSort 函数正在按照预期的方式工作，将列表分开。请参阅以下输出:

Head: lady apple stone red queen
fast:
slow: stone
front: lady apple stone
back: red queen

Head: lady apple stone
fast:
slow: apple
front: lady apple
back: stone

Head: lady apple
fast: 
slow: lady
front: lady
back: apple

Head: red queen
fast:
slow: red
front: red
back: queen

其中清楚地显示了初始列表，lady apple stone red queen被划分为单个节点，全部占。

当节点被比较并合并到新列表中时，问题就来了。例如:最初，lady 被比作 apple。它们被合并到列表中:apple, lady。然后这个列表应该与 stone 合并。但是，首先将 lady 与 stone 进行比较，而不是将 apple 与 stone 进行比较。然后生成列表:lady, stone(apple 被留在后面，未用于比较)。应该发生的是，apple 与 stone 进行比较，然后 lady 与 stone 进行比较，然后是条目被排序并相应地合并到:apple, lady, stone。

实际的最终输出是:lady, red, stone。显然，apple 和 queen 已经丢失了。我不确定有问题的代码是什么。

void mergeSort(Node *head) {

    Node *front = NULL, *back = NULL, *fast, *slow;

    if(head == NULL || head->next == NULL)
        return;

    ...

    mergeSort(front);
    mergeSort(back);

    head = mergeLists(front, back);

}

Answer 1

您的代码几乎是完美的。您正在合并两个列表并将其返回到 head。但是您不会将那个确切的 head 返回到之前的 mergeSort 调用。

Node* mergeSort(Node *head) {

    Node *front = NULL, *back = NULL, *fast, *slow;

    if(head == NULL || head->next == NULL)
        return head; // return head
    ...

    front = mergeSort(front); // save it to front
    back = mergeSort(back); // save it to back

    head = mergeLists(front, back); // save it to head
    return head; // return head
}

在调用 mergeSort 的主函数中，使用 head = mergeSort(head)。代码现在应该可以工作了。