如何合并使用O（nlogn）时间和O（1）空间复杂度对链接列表进行排序

（免责声明：上学）

据我所知，递归拆分链表，然后将其发送到另一个要合并的函数是O（nlogn）时间和O（n）空间。 在O（nlogn）时间和O（1）空间复杂度的链表上是否可以进行合并？ 你会怎么做呢？

任何帮助都表示赞赏

PS：为了确保传统的mergesort是空间复杂度0（n），这是0（n）的一个例子，对吧？ 如何改变O（1）空间？

void sortTrack() { Node merge = this.head; this.head = Node (merge); } public Node mergeSort(Node head){ if ((head == null)||(head.next == null)){ return head; } Node left = head; Node right = head.next; while((right != null) && right.next != null){ head = head.next; right = right.next.next; } right = head.next; head.next = null; return merge(mergeSort(left), mergeSort(right)); } public Node merge(Node left, Node right){ Node head = new Node (); Node temp = head; while((left != null) && (right !=null)){ if(left <= right ){ temp.next = left; temp = left; left = left.next; } else{ temp.next = right; temp = right; right = right.next; } } if(right == null) temp.next = left; else temp.next = right; return head.next; } 

Answer 1

您的递归方法需要Θ（log n ）额外空间，因为当您一直向下合并排序单个列表时，您将在堆栈上进行Θ（log n ）调用。

要将其减少到O（1）额外空间，您需要从递归的“自上而下”方法进行更改，将列表拆分为两个大的子列表，对它们进行排序，并合并结果 – 为您提供递归深度 Θ（log n ） – 迭代的“自下而上”方法，你首先对所有单例列表进行排序，然后是所有对（第一和第二元素，然后第三和第四，等等），然后全部四重奏（第一到第四个元素，然后第五到第八个等） – 给你Θ（log n ）通过列表。 每次传递需要Θ（ n ）时间，因此总时间仍为Θ（ n log n ）。

总的来说，你将有三种方法：

• Node merge(Node listA, Node listB) ，您已经编写过。

• Node mergePass(Node list, int i) ：

  • 前提条件：节点＃1到#n被排序，节点＃（ n + 1）到＃（2 n ）被排序等。
  • 后置条件：节点＃1到＃（2 n ）被排序，节点＃（2 n +1）到＃（4 n ）被排序等。
  • 通过抓取节点＃1到#n和节点＃（ n + 1）到＃（2 n ），“切断”它们，调用merge以及“粘贴”结果来工作; 然后对节点＃（2 n +1）到＃（3 n ）和节点＃（3 n +1）到＃（4 n ）做同样的事情; 等等

• Node mergeSort(Node list) ：

  • 在其参数上调用mergePass(..., 1) 。
  • 在结果上调用mergePass(..., 2) ，然后在该结果上调用mergePass(..., 4)等，每次加倍。
  • 在i是列表的长度（或更大）之前停止，因为mergePass(..., i)是一个no-op，如果i是那么大。
  • 返回最后的结果。