algorithm - 合并单向链表的两半

Question

在一次笔试中，我遇到了一个问题，内容如下:

给定一个整数链表，其前半部分和后半部分都是独立排序的。编写一个函数来合并这两个部分以创建一个单独的排序链表。

约束:不要使用任何额外的空间。

测试用例和输出:
输入列表1:
4->5->6->7->1->2->3;
输出:
1->2->3->4->5->6->7

输入2:
5->6->7->8->1->2->3->4；
输出2:
1->2->3->4->5->6->7->8

我能想到的就是用两个指针:一个用于前半段遍历，一个用于后半段遍历。使用它们，我可以从头到中间(使用第一个指针)和从中间到最后(使用第二个指针)遍历。在同时遍历这两个部分时，我可以比较值并在需要时进行交换。

但是这个解决方案使用了两个消耗内存的指针。

不使用任何内存可以做到吗？

由于这是笔试，我不能要求澄清。
感谢您的帮助。谢谢。

Answer 1

当他们说“不要使用额外空间”时，他们并不是指指针和标量；它们的意思是“数组”和“动态分配的结构”。在您的情况下，内存量是固定的。

合并两个有序列表很简单:首先，将列表切成两半，然后重新排列其元素的 next 指针以使列表排序。

您将需要三个指针 - newHead、head1 和 head2。

• 将head1和head2初始化为原列表的head
• 前进 head2 直到您看到排序序列中的中断(即当 head2->next->value 小于 head2->value)。通过将 head2->next 设置为 NULL 来剪切列表；保留原来的 head2->next - 这是你的新 head2

此时，您有两个独立排序的独立链表，您可以应用经典的合并算法。将newHead设置为head1或head2中较小的元素，然后循环移动，设置next指针当前最后一个元素到 head1 或 head2 中较小的一个。点击 head1->next == NULL 或 head2->next == NULL 后，将另一个列表的头部分配给 next首先用完元素的列表。大功告成 - newHead 现在指向已排序列表的开头。