每周算法-链表排序

发表于 |

题目描述

在leetcode第148道题，在 O(nlogn) 时间复杂度和常数级空间复杂度下，对链表进行排序。链表的数据结构如下：

1
2
3
4
function ListNode(val) {
  this.val = val;
  this.next = null;
}

示例 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
2
3
4
5
6
function ListNode(val) {
  this.val = val;
  this.next = null;
}

var sortList = function (head) {}

上面是leetcode给的模版，其中ListNode构造函数是我放到里面的，因为后面new一个链表节点的时候用到。

使用自底向上的归并排序，首先需要的就是先要知道链表的长度，之后我们再从底部开始依次merge。还是先看代码吧～

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
* @param {ListNode} head 
* @returns {Number} count
*/
const getListCount = (head) => {
  let count = 0;
  let curr = head;
  while (curr) {
    count++;
    curr = curr.next;
  }
  
  return count;
};

以上便是通过while循环计算链表的长度，接下来看如何实现自底向上的拆分链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
var sortList = function (head) {
  const count = getListCount(head);
  const dummyNode = new ListNode(0);
  dummyNode.next = head;

  for (let size = 1; size < count; size += size) {
    let curr = dummyNode.next;
    let prev = dummyNode;
    
    while (curr) {
      const left = curr;
      const right = sliceNode(left, size);
      curr = sliceNode(right, size);
      
      prev.next = merge(left, right);
      while (prev.next) {
        prev = prev.next;
      }
    }
  }
  
  const res = dummyNode.next;
  dummyNode.next = null;
  return res;
}

size作为每次拆分的大小，自底向上的来说就是size的值逐步从1，2，4开始，依次增大2倍，最终小于链表的长度时停止，这样拆分的高度就是logN, 每一轮都会在O(n)的时间复杂度里merge，因此最终的时间复杂度就是O(nlogn)。

现在我们还有两个方法没有实现，一个是sliceNode，一个是merge方法。sliceNode是截断链表，merge是合并两个链表，接下来依次实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const sliceNode = (head, count) => {
  let curr = head;
  while (curr && --count) {
    curr = curr.next;
  }
  
  // 此时剩余的节点数不够count大小，直接返回为null，表明本轮拆分结束
  if (!curr) {
    return null;
  }
  
  // 返回截断后的下一个节点
  const res = curr.next;
  curr.next = null;
  return res;
};

通过sliceNode可以看出，是将head为头的count个节点单独拆出来，和之后的节点不再相连。merge就是将两个节点合并在一起

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const merge = (head1, head2) => {
  const dummyNode = new ListNode(0);
  let curr = dummyNode;
  while (head1 || head2) {
    if (!head1) {
      curr.next = head2;
      head2 = head2.next;
    } else if (!head2) {
      curr.next = head1;
      head1 = head1.next;
    } else if (head1.val < head2.val) {
      curr.next = head1;
      head1 = head1.next;
    } else {
      curr.next = head2;
      head2 = head2.next;
    }
    
    curr = curr.next;
    curr.next = null;
  }
  
  const res = dummyNode.next;
  dummyNode.next = null;
  return res;
};

在merge阶段，通过一个伪造的头节点，使得整个算法更加的简单，要不然就需要针对merge后的新的链表的头节点做各种处理。只不过最后需要取消引用，防止内存泄漏，方便垃圾回收。

以上便是对链表的排序，可以直接提交到leetcode。

番外

既然链表的归并排序已经实现来，增加一个数组的归并排序了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const merge = (arr, left, mid, right) => {
  const aux = [];
  for (let i = left; i <= right; i++) {
    aux[i - left] = arr[i];
  }
  
  let i = left;
  let j = mid + 1;
  for (let k = left; k <= right; k++) {
    if (i > mid) {
      arr[k] = aux[j++];
    } else if (j > right) {
      arr[k] = aux[i++];
    } else if (aux[i] < aux[j]) {
      arr[k] = aux[i++];
    } else {
      arr[k] = aux[j++];
    }
  }
};

const mergeSort = (arr) => {
  const len = arr.length - 1;
  for (let size = 1; size < len; size += size) {
    for (let index = 0; index + size - 1 < len; index += 2 * size) {
      merge(arr, index, index + size - 1, Math.min(len - 1, index + 2 * size - 1));
    }
  }
};

可以看出，数组的自底向上的归并排序和链表的基本思路是一致的，不过要注意的一点是merge(arr, index, index + size - 1, Math.min(len - 1, index + 2 * size - 1)) 在merge阶段，第二个数组的末尾元素的索引需要注意，不能超出入参数组的长度。

-->