在一次笔试中，我遇到一个问题，内容如下：
我们给出了一个整数链表，其中上半部分和下半部分都是独立排序的编写一个函数来合并这两部分以创建一个单独的排序链表。
约束：不要使用任何额外的空间。
测试用例和输出：输入列表1:4->5->6->7->1->2->3；输出：1->2->3->4->5->6->7->8->1->2->3->4->5->6->7->8；输出2:1->2->3->4->5->6->7->8
我能想到的是使用两个指针：一个用于前半个遍历，一个用于后半个遍历。使用它们，我可以从头到中间（使用第一个指针）和从中间到最后（使用第二个指针）。同时遍历两个部分时，我可以比较值并在需要时进行交换。
但是这个解决方案使用了消耗内存的两个指针。
不用记忆就可以完成吗？
由于是笔试，我不能要求澄清。
感谢您的帮助。谢谢。
最佳答案
当他们说“不使用额外的空间”时，他们不是指指针和标量；他们是指“数组”和“动态分配的结构”在您的情况下，内存量是固定的。
合并两个有序列表很简单：首先将列表切成两半，然后重新排列其元素的指针以使列表排序。
您需要三个指针-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现在指向排序列表的开头。