每周算法-链表排序

题目描述

在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阶段,第二个数组的末尾元素的索引需要注意,不能超出入参数组的长度。

-->