在读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
|
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
|
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
|
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
|
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
|
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
|
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
|
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
|
var removeNthFromEnd = function(head, n) {
var dummyNode,
ptr1,
ptr2;
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
|
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
|
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
|
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
|
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
|
var hasCycle = function(head) {
var ptr1,
ptr2;
ptr1 = head;
ptr2 = head;
while (ptr2 !== null && ptr2.next !== null) {
ptr1 = ptr1.next;
ptr2 = ptr2.next.next;
if (ptr1 === ptr2) {
return true;
}
}
return false;
};
|
使用两个指针，一个一次走一步，另一个一次走两步，如果链表存在环的话，两者必然会再次相遇。此外说明下，如果是没有环的情况，当快的指针到达尾结点时，此时慢的指针刚好到达链表的中点。
参考资料