对列表使用归并排序

Question

合并排序可以在列表中进行，而不像数组。
然而，我还没有找到一个参考解释这是如何实现的。

Answer 1

对数组实现就地归并排序实际上是可能的，尽管并不简单。对于链表，这个问题变得非常简单。链表中的每个节点只有一个值和一个指向下一个节点的指针。将链表分成两半是很简单的。只需遍历到中间节点，将其后继节点作为第二个列表的头，然后将后继节点设置为null。

合并步骤就像您期望的那样工作。不要创建任何新节点，只需从两个列表中重新链接节点。