算法专栏 (五)：链表（下）

Go 语言实现链表的技巧

链表的定义是不是很好去理解？但写起来很费劲。这篇文章就结合Go语言和你探讨一下如何写好链表代码，最后用一道经典的链表反转代码来收尾。

写好链表代码需要一些方法和技巧。我根据自己的学习经历和工作经验，总结了几个写链表代码技巧。

技巧一：理解指针或引用的含义

事实上，看懂链表的结构并不是很难，但是一旦把它和指针混在一起，就很容易让人摸不着头脑。所以，要想写对链表代码，首先就要理解好指针。

我们知道，有些语言有“指针”的概念，比如 Go 语言；有些语言没有指针，取而代之的是“引用”，比如 Java、Python。不管是“指针”还是“引用”，实际上，它们的意思都是一样的，都是存储所指对象的内存地址。

接下来，我会拿 Go 语言中的“指针”来讲解，如果你用的是 Java 或者其他没有指针的语言也没关系，你把它理解成“引用”就可以了。

实际上，对于指针的理解，你只需要记住下面这句话就可以了：

将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。

这句话听起来还挺拗口的，你可以先记住。我们回到链表代码的编写过程中，我来慢慢给你解释。

在编写链表代码的时候，我们经常会有这样的代码：p.next=q。这行代码是说，p 结点中的 next 指针存储了 q 结点的内存地址。

还有一个更复杂的，也是我们写链表代码经常会用到的：p.next=p.next.next。这行代码表示，p 结点的 next 指针存储了 p 结点的下下一个结点的内存地址。

技巧二：警惕指针丢失和内存泄漏

不知道你有没有这样的感觉，写链表代码的时候，指针指来指去，一会儿就不知道指到哪里了。所以，我们在写的时候，一定注意不要弄丢了指针。

指针往往都是怎么弄丢的呢？我拿单链表的插入操作为例来给你分析一下。

linklist_next_insert

如图所示，我们希望在结点 a 和相邻的结点 b 之间插入结点 x，假设当前指针 p 指向结点 a。如果我们将代码实现变成下面这个样子，就会发生指针丢失和内存泄露。

1
2
3
p.next = &x  // 将 p 的 next 指针指向 x 结点；
x.next = p.next  // 将 x 的结点的 next 指针指向 b 结点；

p.next 指针在完成第一步操作之后，已经不再指向结点 b 了，而是指向结点 x。第 2 行代码相当于将 x 赋值给 x.next，自己指向自己。因此，整个链表也就断成了两半，从结点 b 往后的所有结点都无法访问到了。

对于有些语言来说，比如 C 语言，内存管理是由程序员负责的，如果没有手动释放结点对应的内存空间，就会产生内存泄露。所以，我们插入结点时，一定要注意操作的顺序，要先将结点 x 的 next 指针指向结点 b，再把结点 a 的 next 指针指向结点 x，这样才不会丢失指针，导致内存泄漏。所以，对于刚刚的插入代码，我们只需要把第 1 行和第 2 行代码的顺序颠倒一下就可以了。

同理，删除链表结点时，也一定要记得手动释放内存空间，否则，也会出现内存泄漏的问题。当然，对于像 Go 这种自动管理内存的编程语言来说，就不需要考虑这么多了。

技巧三：利用哨兵简化实现难度

首先，我们先来回顾一下单链表的插入和删除操作。如果我们在结点 p 后面插入一个新的结点，只需要下面两行代码就可以搞定。

1
2
new_node.next = p.next
p.next = &new_node

即先把新结点指向p 的后结点，再把p的后结点指向新结点，千万不要写反顺序了哦。

但是，当我们要向一个空链表中插入第一个结点，刚刚的逻辑就不能用了。我们需要进行下面这样的特殊处理，其中 head 表示链表的头结点。所以，从这段代码，我们可以发现，对于单链表的插入操作，第一个结点和其他结点的插入逻辑是不一样的。

1
2
3
if head == nil{
  head = new_node
}

。如果要删除结点 p 的后继结点，我们只需要一行代码就可以搞定。

1
2
p.next = p.next.next

但是，如果我们要删除的链表中只剩下最后一个结点，前面的删除代码就不 work 了，因为找不到前节点p 。跟插入类似，我们也需要对于这种情况特殊处理。写成代码是这样子的：

1
2
3
if head.next == nil {
   head = nil
}

从前面的一步一步分析，我们可以看出，针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。这样代码实现起来就会很繁琐，不简洁，而且也容易因为考虑不全而出错。如何来解决这个问题呢？

技巧三中提到的哨兵就要登场了。哨兵，解决的是国家之间的边界问题。同理，这里说的哨兵也是解决“边界问题”的，不直接参与业务逻辑。

还记得如何表示一个空链表吗？head=nil 表示链表中没有结点了。其中 head 表示头结点指针，指向链表中的第一个结点。

如果我们引入哨兵结点，在任何时候，不管链表是不是空，head 指针都会一直指向这个哨兵结点我喜欢叫他根结点。我们也把这种有哨兵结点的链表叫带头链表。相反，没有哨兵结点的链表就叫作不带头链表。

我画了一个带头链表，你可以发现，哨兵结点是不存储数据的。因为哨兵结点一直存在，所以插入第一个结点其实就是在根结点后插入一个结点，删除最后一个结点，都可以统一为其实就是删除根接电后的一个节点，和处理其他位置的结点为相同的代码实现逻辑。

linklist_next_root

我用Go写了一个获取数组对应值下标的代码来进行一个简单的利用哨兵简化代码时间复杂度的解释：

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

// 使用哨兵的例子
// 查询某个值在数组中的下标
func GetIndexOfArray(list []int, key int) int {
	if list == nil {
		return -1
	}

	for i := 0; i < len(list); i++ {
		if list[i] == key {
			return i
		}
	}

	return -1

}

func GetIndexOfArray2(list []int, key int) int {
  if list==nil{
     return -1
  }
  
	// 缓存最后一个值
	n := len(list)
	tmp := list[n-1]

	// 将 key 付给最后一个值作为哨兵
	list[n-1] = key
	if tmp == key {
		return n - 1
	}

	i := 0
	for {
		if list[i] == key {
			break
		}
		i++
	}

	// 恢复原数组
	list[n-1] = tmp
	
	if i == n-1 {
		return -1
	}

	return i
}

第一个例子是传统的写法，第二个例子是利用哨兵思想的写法，这两个例子看起来反而利用哨兵的更加复杂，但是如果你学会了时间复杂度分析你会直接去看for循环的代码，相对于没有进行哨兵处理的代码1，进行哨兵处理的代码每次都要进行i < n与否的判断，如果数组存储了极大量的数据那么哨兵的写法的优势就凸显出来了。

技巧四：重点留意边界条件处理

软件开发中，代码在一些边界或者异常情况下，最容易产生 Bug。链表代码也不例外。要实现没有 Bug 的链表代码，一定要在编写的过程中以及编写完成之后，检查边界条件是否考虑全面，以及代码在边界条件下是否能正确运行。

我经常用来检查链表代码是否正确的边界条件有这样几个：

  • 如果链表为空时，代码是否能正常工作？
  • 如果链表只包含一个结点时，代码是否能正常工作？
  • 如果链表只包含两个结点时，代码是否能正常工作？
  • 代码逻辑在处理头结点和尾结点的时候，是否能正常工作？

当你写完链表代码之后，除了看下你写的代码在正常的情况下能否工作，还要看下在上面我列举的几个边界条件下，代码仍然能否正确工作。如果这些边界条件下都没有问题，那基本上可以认为没有问题了。

当然，边界条件不止我列举的那些。针对不同的场景，可能还有特定的边界条件，这个需要你自己去思考，不过套路都是一样的。

实际上，不光光是写链表代码，你在写任何代码时，也千万不要只是实现业务正常情况下的功能就好了，一定要多想想，你的代码在运行的时候，可能会遇到哪些边界情况或者异常情况。遇到了应该如何应对，这样写出来的代码才够健壮！

技巧五：举例画图，辅助思考

对于稍微复杂的链表操作，比如前面我们提到的单链表反转，指针一会儿指这，一会儿指那，一会儿就被绕晕了。总感觉脑容量不够，想不清楚。所以这个时候就要使用大招了，举例法和画图法。

你可以找一个具体的例子，把它画在纸上，释放一些脑容量，留更多的给逻辑思考，这样就会感觉到思路清晰很多。比如往单链表中插入一个数据这样一个操作，我一般都是把各种情况都举一个例子，画出插入前和插入后的链表变化，如图所示：

linklist_next_example

看图写代码，是不是就简单多啦？而且，当我们写完代码之后，也可以举几个例子，画在纸上，照着代码走一遍，很容易就能发现代码中的 Bug。

技巧六：多写多练，没有捷径

如果你已经理解并掌握了我前面所讲的方法，但是手写链表代码还是会出现各种各样的错误，也不要着急。因为我最开始学的时候，这种状况也持续了一段时间。

现在我写这些代码，简直就和“玩儿”一样，其实也没有什么技巧，就是把常见的链表操作都自己多写几遍，出问题就一点一点调试，熟能生巧！

所以，我精选了 5 个常见的链表操作。你只要把这几个操作都能写熟练，不熟就多写几遍，我保证你之后再也不会害怕写链表代码。

  • 单链表反转
  • 链表中环的检测
  • 两个有序的链表合并
  • 删除链表倒数第 n 个结点
  • 求链表的中间结点

Go 语言实现链表代码

单向链表

其实每种数据结构的接口都是可以根据你的需求进行定义的，比如单向链表，我们需要他实现什么方法呢？初始化，插入，删除，对某个值后面插入链表等等，我把可能的操作接口都尽可能写出来：

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
// 单链表代码
type Object interface{}

type Node struct {
	Data Object
	next *Node
}

type ListSingle struct {
	size uint64
	head *Node
	tail *Node
}

func (list *ListSingle) Init() {
	(*list).size = 0
	(*list).head = nil
	(*list).tail = nil
}

// 向链表追加节点
func (list *ListSingle) Append(node *Node) bool {
	if node == nil {
		return false
	}

	(*node).next = nil // 新加节点在末尾，没有next
	if (*list).size == 0 {
		(*list).head = node
	} else {
		oldTail := (*list).tail // 取尾结点
		(*oldTail).next = node  // 尾结点的next指向新加节点
	}

	(*list).tail = node // 新节点是尾结点
	(*list).size++
	return true
}

// 向第i个节点处插入节点
func (list *ListSingle) Insert(i uint64, node *Node) bool {
	if node == nil || i > (*list).size || (*list).size == 0 {
		return false
	}

	if i == 0 {
		(*node).next = (*list).head
		(*list).head = node
	} else {
		preNode := (*list).head
		for j := uint64(1); j < i; j++ {
			preNode = (*preNode).next
		}

		(*node).next = (*preNode).next // 新节点指向旧节点原来所指的next
		(*preNode).next = node         // 原节点的next指向新节点
	}
	(*list).size++

	return true
}

// 移除指定位置的节点
func (list *ListSingle) Remove(i uint64) bool {
	if i >= (*list).size {
		return false
	}

	if i == 0 {
		preHead := (*list).head     // 取出旧的链表头
		(*list).head = preHead.next // 旧链表头的next变为新的头

		// 如果仅有一个节点，则头尾节点清空
		if (*list).size == 1 {
			(*list).head = nil
			(*list).tail = nil
		}
	} else {
		preNode := (*list).head
		for j := uint64(1); j < i; j++ {
			preNode = (*preNode).next
		}

		node := (*preNode).next     // 找到当前要删除的节点
		(*preNode).next = node.next // 把当前要删除节点的next赋给其父节点的next,完成后代转移

		// 若删除的尾部，尾部指针需要调整
		if i == ((*list).size - 1) {
			(*list).tail = preNode
		}
	}

	(*list).size--

	return true
}

// 移除所有节点
func (list *ListSingle) RemoveAll() bool {
	(*list).Init()
	return true
}

// 获取指定位置的节点
func (list *ListSingle) Get(i uint64) *Node {
	if i >= (*list).size {
		return nil
	}

	node := (*list).head
	for j := uint64(0); j < i; j++ {
		node = (*node).next
	}

	return node
}

// 搜索某个数据的节点位置
func (list *ListSingle) IndexOf(data Object) int64 {
	pos := int64(-1)
	node := (*list).head
	if node.Data == data {
		return 0
	}

	for j := uint64(1); j < (*list).size; j++ {
		if node != nil {
			node = (*node).next
			if node != nil && node.Data == data {
				pos = int64(j)
				break
			}
		}
	}
	return pos
}

// 取得链表长度
func (list *ListSingle) GetSize() uint64 {
	return (*list).size
}

// 取得链表头
func (list *ListSingle) GetHead() *Node {
	return (*list).head
}

// 取得链表尾
func (list *ListSingle) GetTail() *Node {
	return (*list).tail
}

这个代码是不进行哨兵结点优化的代码，大家可以尝试写一下进行哨兵结点优化的代码。

双向链表

双向链表我直接拿的 go 官方库 container/list 的代码，写的非常好，也同时进行了哨兵结点的优化，你可以看下你的优化是否和他的一样。

地址我放在这 container/list

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
package link_list

// Element is an element of a linked list.
type Element struct {
	// Next and previous pointers in the doubly-linked list of elements.
	// To simplify the implementation, internally a list l is implemented
	// as a ring, such that &l.root is both the next element of the last
	// list element (l.Back()) and the previous element of the first list
	// element (l.Front()).
	next, prev *Element

	// The list to which this element belongs.
	list *List

	// The value stored with this element.
	Value interface{}
}

// Next returns the next list element or nil.
func (e *Element) Next() *Element {
	if p := e.next; e.list != nil && p != &e.list.root {
		return p
	}
	return nil
}

// Prev returns the previous list element or nil.
func (e *Element) Prev() *Element {
	if p := e.prev; e.list != nil && p != &e.list.root {
		return p
	}
	return nil
}

// List represents a doubly linked list.
// The zero value for List is an empty list ready to use.
type List struct {
	root Element // sentinel list element, only &root, root.prev, and root.next are used
	len  int     // current list length excluding (this) sentinel element
}

// Init initializes or clears list l.
func (l *List) Init() *List {
	l.root.next = &l.root
	l.root.prev = &l.root
	l.len = 0
	return l
}

// New returns an initialized list.
func New() *List { return new(List).Init() }

// Len returns the number of elements of list l.
// The complexity is O(1).
func (l *List) Len() int { return l.len }

// Front returns the first element of list l or nil if the list is empty.
func (l *List) Front() *Element {
	if l.len == 0 {
		return nil
	}
	return l.root.next
}

// Back returns the last element of list l or nil if the list is empty.
func (l *List) Back() *Element {
	if l.len == 0 {
		return nil
	}
	return l.root.prev
}

// lazyInit lazily initializes a zero List value.
func (l *List) lazyInit() {
	if l.root.next == nil {
		l.Init()
	}
}

// insert inserts e after at, increments l.len, and returns e.
func (l *List) insert(e, at *Element) *Element {
	e.prev = at
	e.next = at.next
	e.prev.next = e
	e.next.prev = e
	e.list = l
	l.len++
	return e
}

// insertValue is a convenience wrapper for insert(&Element{Value: v}, at).
func (l *List) insertValue(v interface{}, at *Element) *Element {
	return l.insert(&Element{Value: v}, at)
}

// remove removes e from its list, decrements l.len, and returns e.
func (l *List) remove(e *Element) *Element {
	e.prev.next = e.next
	e.next.prev = e.prev
	e.next = nil // avoid memory leaks
	e.prev = nil // avoid memory leaks
	e.list = nil
	l.len--
	return e
}

// move moves e to next to at and returns e.
func (l *List) move(e, at *Element) *Element {
	if e == at {
		return e
	}
	e.prev.next = e.next
	e.next.prev = e.prev

	e.prev = at
	e.next = at.next
	e.prev.next = e
	e.next.prev = e

	return e
}

// Remove removes e from l if e is an element of list l.
// It returns the element value e.Value.
// The element must not be nil.
func (l *List) Remove(e *Element) interface{} {
	if e.list == l {
		// if e.list == l, l must have been initialized when e was inserted
		// in l or l == nil (e is a zero Element) and l.remove will crash
		l.remove(e)
	}
	return e.Value
}

// PushFront inserts a new element e with value v at the front of list l and returns e.
func (l *List) PushFront(v interface{}) *Element {
	l.lazyInit()
	return l.insertValue(v, &l.root)
}

// PushBack inserts a new element e with value v at the back of list l and returns e.
func (l *List) PushBack(v interface{}) *Element {
	l.lazyInit()
	return l.insertValue(v, l.root.prev)
}

// InsertBefore inserts a new element e with value v immediately before mark and returns e.
// If mark is not an element of l, the list is not modified.
// The mark must not be nil.
func (l *List) InsertBefore(v interface{}, mark *Element) *Element {
	if mark.list != l {
		return nil
	}
	// see comment in List.Remove about initialization of l
	return l.insertValue(v, mark.prev)
}

// InsertAfter inserts a new element e with value v immediately after mark and returns e.
// If mark is not an element of l, the list is not modified.
// The mark must not be nil.
func (l *List) InsertAfter(v interface{}, mark *Element) *Element {
	if mark.list != l {
		return nil
	}
	// see comment in List.Remove about initialization of l
	return l.insertValue(v, mark)
}

// MoveToFront moves element e to the front of list l.
// If e is not an element of l, the list is not modified.
// The element must not be nil.
func (l *List) MoveToFront(e *Element) {
	if e.list != l || l.root.next == e {
		return
	}
	// see comment in List.Remove about initialization of l
	l.move(e, &l.root)
}

// MoveToBack moves element e to the back of list l.
// If e is not an element of l, the list is not modified.
// The element must not be nil.
func (l *List) MoveToBack(e *Element) {
	if e.list != l || l.root.prev == e {
		return
	}
	// see comment in List.Remove about initialization of l
	l.move(e, l.root.prev)
}

// MoveBefore moves element e to its new position before mark.
// If e or mark is not an element of l, or e == mark, the list is not modified.
// The element and mark must not be nil.
func (l *List) MoveBefore(e, mark *Element) {
	if e.list != l || e == mark || mark.list != l {
		return
	}
	l.move(e, mark.prev)
}

// MoveAfter moves element e to its new position after mark.
// If e or mark is not an element of l, or e == mark, the list is not modified.
// The element and mark must not be nil.
func (l *List) MoveAfter(e, mark *Element) {
	if e.list != l || e == mark || mark.list != l {
		return
	}
	l.move(e, mark)
}

// PushBackList inserts a copy of another list at the back of list l.
// The lists l and other may be the same. They must not be nil.
func (l *List) PushBackList(other *List) {
	l.lazyInit()
	for i, e := other.Len(), other.Front(); i > 0; i, e = i-1, e.Next() {
		l.insertValue(e.Value, l.root.prev)
	}
}

// PushFrontList inserts a copy of another list at the front of list l.
// The lists l and other may be the same. They must not be nil.
func (l *List) PushFrontList(other *List) {
	l.lazyInit()
	for i, e := other.Len(), other.Back(); i > 0; i, e = i-1, e.Prev() {
		l.insertValue(e.Value, &l.root)
	}
}

经典习题链表反转

最后用一道链表反转的习题来结束链表的总结，该提给出了两种解答的方式，双指针和递归的方式。

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
30
31
32
type ListNode struct {
	Val  int
	Next *ListNode
}

//双指针
func ReverseList(head *ListNode) *ListNode {
	var pre *ListNode
	cur := head
	for cur != nil {
		next := cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}
	return pre
}

//递归
func ReverseList2(head *ListNode) *ListNode {
	return help(nil, head)
}

func help(pre, head *ListNode) *ListNode {
	if head == nil {
		return pre
	}
	next := head.Next
	head.Next = pre
	return help(head, next)
}