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

此实现用于按字母升序排列字符串。我包含了负责划分节点的函数。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);

}

最佳答案

你的代码几乎是完美的。您正在合并两个列表并将其返回到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)。代码现在应该可以工作了。