上一节我们介绍了线性表的顺序存储实现，这一节阐述线性表的链式存储实现。
链表
链表由一系列不必在内存中物理相连的结构组成，每个结构都包含一个数据元素和一个指向下一个结构的指针。
根据指针的指向和数量，链表通常又可分为单链表、双向链表和循环链表。
实际使用中，双向链表更为常用。
若我们直接对第一个结构进行操作，那么编程会出现一些麻烦的问题，例如：
- 如何在首结构前插入？
- 如何删除首结构？
要么这些操作很难完成，要么需要在函数中特殊对待，这为编程提供了挑战。事实上只要在首结构前加入一个 Header 就可以很好的解决了。
许多时候我们约定 Header 作为位置 0，虽然我个人不喜欢这种做法。
单链表
单链表的节点结构可以表示为：
1type Node struct {
2 Data interface{}
3 Next *Node
4}
显然的，链表的访问方式与顺序表非常不同，因此代码也有很大变化。
初始化
1func New() *Node {
2 return &Node{}
3}
取值
1func (n *Node) Get(i int) (interface{}, error) {
2 if i < 0 {
3 return nil, errors.New("index out of range")
4 }
5 for j := 0; j < i; j++ {
6 n = n.Next
7 if n == nil {
8 return nil, errors.New("index out of range")
9 }
10 }
11 return n.Data, nil
12}
插入
1func (n *Node) Insert(i int, data interface{}) error {
2 if i < 0 {
3 return errors.New("index out of range")
4 }
5 for j := 0; j < i; j++ {
6 n = n.Next
7 if n == nil {
8 return errors.New("index out of range")
9 }
10 }
11 n.Next = &Node{Data: data, Next: n.Next}
12 return nil
13}
删除
1func (n *Node) Delete(i int) error {
2 if i < 0 {
3 return errors.New("index out of range")
4 }
5 for j := 0; j < i; j++ {
6 n = n.Next
7 if n == nil {
8 return errors.New("index out of range")
9 }
10 }
11 n.Next = n.Next.Next
12 return nil
13}
创建链表
创建链表根据节点插入位置的不同，可以分为头插法和尾插法。
头插法：
1func CreateHead(data []interface{}) *Node {
2 var head *Node = nil
3 for _, v := range data {
4 head := &Node{Data: v, Next: head}
5 }
6 return head
7}
尾插法：
1func CreateTail(data []interface{}) *Node {
2 var head *Node = nil
3 var tail *Node = nil
4 for _, v := range data {
5 if head == nil {
6 head = &Node{Data: v, Next: nil}
7 tail = head
8 } else {
9 tail.Next = &Node{Data: v, Next: nil}
10 tail = tail.Next
11 }
12 }
13 return head
14}
双向链表
双向链表的节点结构可以表示为：
1type Node struct {
2 Data interface{}
3 Prev *Node
4 Next *Node
5}
即每个节点多维护一个指向前一个节点的指针。
每次插入或删除节点时，需要同时修改前后节点的指针。
循环链表
循环链表即为首尾相连的链表，即首节点的前驱为尾节点，尾节点的后继为首节点。
与单链表相比，最大的区别在于遍历的边界条件不同。
在循环链表中，以首节点为起点，遍历到尾节点时，尾节点的后继为首节点，因此遍历的边界条件为：
1for n.Next != head {
2 // ...
3}
一些练习
LeetCode 707 设计链表
一道链表设计题，基本涵盖了链表的常用操作。
不要小看这道题，好好写完这道链表题你会发现实现链表过程中有很多边界条件是不好掌握的。
1type MyLinkedList struct {
2 Val int
3 Next *MyLinkedList
4}
5
6
7func Constructor() MyLinkedList {
8 // return a dummy node
9 return MyLinkedList{
10 Val: -1,
11 Next: nil,
12 }
13}
14
15
16func (this *MyLinkedList) Get(index int) int {
17 cur := this.Next
18 for i := 0; cur != nil; i++ {
19 if i == index {
20 return cur.Val
21 } else {
22 cur = cur.Next
23 }
24 }
25 return -1
26}
27
28
29func (this *MyLinkedList) AddAtHead(val int) {
30 new := &MyLinkedList{
31 Val: val,
32 Next: this.Next,
33 }
34 this.Next = new
35 return
36}
37
38
39func (this *MyLinkedList) AddAtTail(val int) {
40 cur := this
41 for cur.Next != nil {
42 cur = cur.Next
43 }
44 new := &MyLinkedList{
45 Val: val,
46 Next: nil,
47 }
48 cur.Next = new
49}
50
51
52func (this *MyLinkedList) AddAtIndex(index int, val int) {
53 if index < 0 {
54 this.AddAtHead(val)
55 return
56 }
57 if index == 0 {
58 this.AddAtHead(val)
59 return
60 }
61 cur := this
62 for i := 0; i < index; i++ {
63 if cur.Next != nil {
64 cur = cur.Next
65 } else {
66 if i == index {
67 this.AddAtTail(val)
68 return
69 } else {
70 return
71 }
72 }
73 }
74 new := &MyLinkedList{
75 Val: val,
76 Next: cur.Next,
77 }
78 cur.Next = new
79}
80
81
82func (this *MyLinkedList) DeleteAtIndex(index int) {
83 cur := this
84 for i := 0; i < index; i++ {
85 if cur.Next == nil {
86 return
87 }
88 cur = cur.Next
89 }
90 if cur.Next != nil {
91 cur.Next = cur.Next.Next
92 }
93 return
94}
95
96
97/**
98 * Your MyLinkedList object will be instantiated and called as such:
99 * obj := Constructor();
100 * param_1 := obj.Get(index);
101 * obj.AddAtHead(val);
102 * obj.AddAtTail(val);
103 * obj.AddAtIndex(index,val);
104 * obj.DeleteAtIndex(index);
105 */
这是一个普通的单链表实现，把它改成双向链表也不是很困难，留给各位读者作为思考题。
LeetCode 21 合并两个有序链表
这是一道基础题目，也是教材上的一道例题。
1func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
2 dummy := &ListNode{}
3 cur := dummy
4 l1 := list1
5 l2 := list2
6 for l1 != nil && l2 != nil {
7 // 如果 list1 小，把 list1 节点接过来，反之依然
8 if l1.Val < l2.Val {
9 cur.Next = l1
10 l1 = l1.Next
11 } else {
12 cur.Next = l2
13 l2 = l2.Next
14 }
15 // cur 后移
16 cur = cur.Next
17 }
18 // 如果 list1 和 list2 还有剩余，把剩余的节点接到后面
19 if l1 != nil {
20 cur.Next = l1
21 }
22 if l2 != nil {
23 cur.Next = l2
24 }
25
26 return dummy.Next
27}
LeetCode 203 移除链表元素
同样是基础题目，遍历一遍遇到就删就可以了。
1func removeElements(head *ListNode, val int) *ListNode {
2 dummy := &ListNode{
3 Val: -1,
4 Next: head,
5 }
6 cur := dummy
7 for cur.Next != nil {
8 if cur.Next.Val == val {
9 cur.Next = cur.Next.Next
10 } else {
11 cur = cur.Next
12 }
13 }
14 return dummy.Next
15}
LeetCode 19 删除链表的倒数第 N 个结点
如果能够事先知道链表的长度，这道题非常简单，本质上变成小学数学题了。但通常拿到一个链表只能知道链表的头指针，而不知道链表的长度。
这道题又是一个双指针。实现非常巧妙，我们使用两个指针，第一个指针从链表的头指针开始遍历向前走 n 步，第二个指针保持不动；从第 $n+1$ 步开始，第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在 n 步，当第一个指针到达链表的尾结点时，第二个指针正好是倒数第 n 个结点。
1func removeNthFromEnd(head *ListNode, n int) *ListNode {
2 dummy := &ListNode{
3 Val: -1,
4 Next: head,
5 }
6 fast := dummy
7 slow := dummy
8 for i := 0; i < n; i++ {
9 fast = fast.Next
10 }
11
12 for fast.Next != nil {
13 slow = slow.Next
14 fast = fast.Next
15 }
16 slow.Next = slow.Next.Next
17 return dummy.Next
18}
LeetCode 83 删除排序链表中的重复元素
又是简单题目。最简单的解法是遍历链表，如果当前结点的值和下一个结点的值相同，就删除下一个结点。
由于这道题要至少保留一个节点，不会出现删除头节点的情况，所以不需要使用虚拟头结点。
1func deleteDuplicates(head *ListNode) *ListNode {
2 cur := head
3 for cur != nil && cur.Next != nil {
4 if cur.Val == cur.Next.Val {
5 cur.Next = cur.Next.Next
6 } else {
7 cur = cur.Next
8 }
9 }
10 return head
11}
评论