2


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

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

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

测试用例和输出：
输入List1：
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

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

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

可以在不使用任何内存的情况下完成吗？

由于是笔试，我不能要求澄清。
协助表示赞赏。谢谢。

4

1 回答 1

4

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

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

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

  • 初始化head1和head2到head原始列表的
  • 前进head2，直到您看到排序序列中的中断（即，当head2->next->value小于时head2->value）。通过将列表设置head2->next为NULL; 保留原件head2->next- 这是您的新品head2

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

于 2012-12-21T11:33:33.363 回答