剖析链表,链表常用操作集合

在读SICP的时候,我就接触了里面的基本数据结构序对(Pairs),那时还没有学习数据结构,没想到就是链表。链表是一种递归的数据结构,Scheme是一种函数式编程语言,Scheme程序随处可见递归,用它来做基本的数据结构再合适不过了。本文介绍的链表操作多数来源于LeetCode上链表专题上的算法题。

数组和链表

数组和链表都是线性数据结构,但和数组不同的是,链表不是连续存储,需要额外的空间来存储结点间的逻辑关系。数组很常见,常见语言中数组都有实现,是基本的数据结构。与链表相比,它不要额外内存、支持随即访问,但也有缺点,首先是需要预先分配空间,再次是插入、删除操作成本太高,需要频繁移动。链表则是完全相反,数组的缺点都是它的长处。

查找

链表结点的实现如下,各个操作都基于这个结点实现。

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

在链表中查找一个值,因为链表的结构特性,使用for语句可以很自然地完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/

var getNode = function(head, n) {
var ptr;

for (ptr = head; ptr !== null; ptr = ptr.next) {
if (n === ptr.val) {
return ptr;
}
}
return null;
};

删除

删除含有给定值的所有结点

给定链表,删除链表中和给定值相等的所有结点,详细描述见

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
30
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/

var removeElements = function(head, n) {
var ptr,
prev;

if (head === null) {
return null;
}

ptr = head;
prev = null;
while (ptr !== null && n === ptr.val) {
head = ptr.next;
ptr = ptr.next;
}

for (; ptr !== null; ptr = ptr.next) {
if (n === ptr.val) {
prev.next = ptr.next;
} else {
prev = ptr;
}
}
return head;
};

上面while语句是处理边界情况的,就是当链表开头的结点都是要删除的结点时的情况,还有另一种处理方法,使用哑结点,可以便利处理边界情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/

var removeElements = function(head, n) {
var dummyNode,
prev;

dummyNode = new ListNode(0);
dummyNode.next = head;
prev = dummyNode;
for (; head !== null; head = head.next) {
if (n === head.val) {
prev.next = head.next;
} else {
prev = head;
}
}
return dummyNode.next;
};

最后的递归大法,简洁优雅。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/

var removeElements = function(head, n) {
if (head === null) {
return null;
}
if (n === head.val) {
head = removeElements(head.next, n);
} else {
head.next = removeElements(head.next, n);
}
return head;
};

删除重复结点

给定有序链表,删除链表中的所有重复项,详细描述见

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* @param {ListNode} head
* @return {ListNode}
*/

var deleteDuplicates = function(head) {
var ptr;

ptr = head;
while (ptr !== null && ptr.next !== null) {
if (ptr.val === ptr.next.val) {
ptr.next = ptr.next.next;
} else {
ptr = ptr.next;
}
}
return head;
};

递归思路和上面类似,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* @param {ListNode} head
* @return {ListNode}
*/

var deleteDuplicates = function(head) {
if (head === null || head.next === null) {
return head;
}
if (head.val === head.next.val) {
head = deleteDuplicates(head.next);
} else {
head.next = deleteDuplicates(head.next);
}
return head;
};

删除倒数第n个结点

给定链表,从列表末尾删除第n个结点,题目详细描述见

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
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/

var removeNthFromEnd = function(head, n) {
var dummyNode,
len;

dummyNode = new ListNode(0);
dummyNode.next = head;
len = 0;
while (head !== null) {
len++;
head = head.next;
}
len = len - n;
head = dummyNode;
while (len-- > 0) {
head = head.next;
}
head.next = head.next.next;
return dummyNode.next;
};

此题有一个直观的解法,先求出链表的长度,然后得出在顺序的情况下此结点的位置,最后将它删除。此方法扫描链表两遍,但要求只能扫描一遍呢,我们可以使用两个指针,对一个指针延迟n步,当快的指针到达链表终点时,延迟的指针便指向待删除的结点。

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
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/

var removeNthFromEnd = function(head, n) {
var dummyNode,
ptr1, // quick one
ptr2; // slow one

dummyNode = new ListNode(0);
dummyNode.next = head;
ptr1 = head;
ptr2 = dummyNode;

while (n-- > 0) {
ptr1 = ptr1.next;
}
while (ptr1 !== null) {
ptr1 = ptr1.next;
ptr2 = ptr2.next;
}

ptr2.next = ptr2.next.next;
return dummyNode.next;
};

反转链表

反转一个单向链表,先是迭代版本的,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* @param {ListNode} head
* @return {ListNode}
*/

var reverseList = function(head) {
var prev,
next;

if (head === null || head.next === null) {
return head;
}

prev = null;
next = null;
while (head !== null) {
next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
};

下面是递归版本的,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* @param {ListNode} head
* @return {ListNode}
*/

var reverseList = function(head) {
var newHead;

if (head === null || head.next === null) {
return head;
}

newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
};

与反转相关的操作还有判断单链表是否回文,有一种算法是,先找出链表的中点,然后反转链表的后半部分,最后前、后两部分进行比较;当然,还可以充分利用栈的性质。

归并有序链表

归并两个有序的单向链表,题目详细描述见

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
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/

var mergeTwoLists = function(l1, l2) {
var dummyNode,
ptr;

dummyNode = new ListNode(0);
ptr = dummyNode;
while (l1 !== null && l2 !== null) {
if (l1.val < l2.val) {
ptr.next = l1;
l1 = l1.next;
} else {
ptr.next = l2;
l2 = l2.next;
}
ptr = ptr.next;
}
ptr.next = l1 || l2;
return dummyNode.next;
};

算法思想很简单,依次比较两个链表的每个结点。《算法4》讲过一种归并多个输入流的算法,使用的是一种特殊的优先队列。注意,上述代码的倒数第二行,JS中,由于逻辑或的特性,ptr.next将会被赋予等号后面两个值中的一个。

链表的交集

给定两个单链表,寻找链表的交集,详细描述在

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* @param {ListNode} headA
* @param {ListNode} headB
* @return {ListNode}
*/

var getIntersectionNode = function(headA, headB) {
var ptr1,
ptr2;

if (headA === null || headB === null) {
return null;
}

ptr1 = headA;
ptr2 = headB;
while (ptr1 !== ptr2) {
ptr1 = (ptr1 === null ? headB : ptr1.next);
ptr2 = (ptr2 === null ? headA : ptr2.next);
}
return ptr1;
};

此算法的核心是对每个链表遍历了两次,第一次的遍历弥补了两条链表长度的差异。开始,两个指针分别指向两条链表的首结点,当指针到达尾结点时,便指向另一条链表的首结点;之后,如果两指针相等,那么该结点就是所求的结点,如果两条链表没有交集,则两个指针都会再次到达尾结点,循环结束,返回null。不信的话,可以在纸上画画演算下。

判断是否有环

给定链表判断是否有环,详细见

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* @param {ListNode} head
* @return {boolean}
*/

var hasCycle = function(head) {
var ptr1, // slow one
ptr2; // quick one

ptr1 = head;
ptr2 = head;
while (ptr2 !== null && ptr2.next !== null) {
ptr1 = ptr1.next;
ptr2 = ptr2.next.next;
if (ptr1 === ptr2) {
return true;
}
}
return false;
};

使用两个指针,一个一次走一步,另一个一次走两步,如果链表存在环的话,两者必然会再次相遇。此外说明下,如果是没有环的情况,当快的指针到达尾结点时,此时慢的指针刚好到达链表的中点。


参考资料

Copyright © 2021 DukeLuo Blog

Powered by Hexo • Theme Candelas