题目描述
在leetcode第148道题,在 O(nlogn) 时间复杂度和常数级空间复杂度下,对链表进行排序。链表的数据结构如下:
1 | function ListNode(val) { |
示例 1:
输入: 4->2->1->3
输出: 1->2->3->4
示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5
分析
排序是一个非常熟悉的内容,使用的基本排序算法也都是针对数组来实现的,但是若想要针对链表,相应的思想应该是一致的。那继续梳理一下O(nlogn)的时间复杂度的排序,基本都知道的有归并排序,快排。在系统级别实现一般是快排,但是快排需要使用数组的索引,而对链表来说就不适用。
那继续看下归并,其中归并有两种思路,一种是自顶向下的归并,通过自顶向下的二分,最后在逐步向上合并,这种思路也是需要使用到数组的索引。另一种思路那就是自底向上的归并,这种思路其实比较适用于链表的排序。使用归并,时间复杂度是O(nlogn),但是在merge阶段,需要开辟一个O(n)的空间,这是针对数组的排序的,对于链表来说,并不需要O(n)的空间。
实现
接下来看下如何实现
1 | function ListNode(val) { |
上面是leetcode给的模版,其中ListNode构造函数是我放到里面的,因为后面new一个链表节点的时候用到。
使用自底向上的归并排序,首先需要的就是先要知道链表的长度,之后我们再从底部开始依次merge。还是先看代码吧~
1 | /* |
以上便是通过while循环计算链表的长度,接下来看如何实现自底向上的拆分链表
1 | var sortList = function (head) { |
size作为每次拆分的大小,自底向上的来说就是size的值逐步从1,2,4开始,依次增大2倍,最终小于链表的长度时停止,这样拆分的高度就是logN, 每一轮都会在O(n)的时间复杂度里merge,因此最终的时间复杂度就是O(nlogn)。
现在我们还有两个方法没有实现,一个是sliceNode,一个是merge方法。sliceNode是截断链表,merge是合并两个链表,接下来依次实现
1 | const sliceNode = (head, count) => { |
通过sliceNode可以看出,是将head为头的count个节点单独拆出来,和之后的节点不再相连。merge就是将两个节点合并在一起
1 | const merge = (head1, head2) => { |
在merge阶段,通过一个伪造的头节点,使得整个算法更加的简单,要不然就需要针对merge后的新的链表的头节点做各种处理。只不过最后需要取消引用,防止内存泄漏,方便垃圾回收。
以上便是对链表的排序,可以直接提交到leetcode。
番外
既然链表的归并排序已经实现来,增加一个数组的归并排序了
1 | const merge = (arr, left, mid, right) => { |
可以看出,数组的自底向上的归并排序和链表的基本思路是一致的,不过要注意的一点是merge(arr, index, index + size - 1, Math.min(len - 1, index + 2 * size - 1))
在merge阶段,第二个数组的末尾元素的索引需要注意,不能超出入参数组的长度。