链表

基本技能

链表相关的核心点
  • null/nil 异常处理
  • dummy node 哑巴节点
  • 快慢指针
  • 插入一个节点到排序链表
  • 从一个链表中移除一个节点
  • 翻转链表
  • 合并两个链表
  • 找到链表的中间节点

常见题型

给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。
1
func deleteDuplicates(head *ListNode) *ListNode {
2
current := head
3
for current != nil {
4
// 全部删除完再移动到下一个元素
5
for current.Next != nil && current.Val == current.Next.Val {
6
current.Next = current.Next.Next
7
}
8
current = current.Next
9
}
10
return head
11
}
Copied!
给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现的数字。
思路:链表头结点可能被删除,所以用 dummy node 辅助删除
1
func deleteDuplicates(head *ListNode) *ListNode {
2
if head == nil {
3
return head
4
}
5
dummy := &ListNode{Val: 0}
6
dummy.Next = head
7
head = dummy
8
​
9
var rmVal int
10
for head.Next != nil && head.Next.Next != nil {
11
if head.Next.Val == head.Next.Next.Val {
12
// 记录已经删除的值,用于后续节点判断
13
rmVal = head.Next.Val
14
for head.Next != nil && head.Next.Val == rmVal {
15
head.Next = head.Next.Next
16
}
17
} else {
18
head = head.Next
19
}
20
}
21
return dummy.Next
22
}
Copied!
注意点 • A->B->C 删除 B,A.next = C • 删除用一个 Dummy Node 节点辅助(允许头节点可变) • 访问 X.next 、X.value 一定要保证 X != nil
反转一个单链表。
思路:用一个 prev 节点保存向前指针,temp 保存向后的临时指针
1
func reverseList(head *ListNode) *ListNode {
2
var prev *ListNode
3
for head != nil {
4
// 保存当前head.Next节点,防止重新赋值后被覆盖
5
// 一轮之后状态:nil<-1 2->3->4
6
// prev head
7
temp := head.Next
8
head.Next = prev
9
// pre 移动
10
prev = head
11
// head 移动
12
head = temp
13
}
14
return prev
15
}
Copied!
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
思路:先遍历到 m 处,翻转,再拼接后续,注意指针处理
1
func reverseBetween(head *ListNode, m int, n int) *ListNode {
2
// 思路:先遍历到m处,翻转,再拼接后续,注意指针处理
3
// 输入: 1->2->3->4->5->NULL, m = 2, n = 4
4
if head == nil {
5
return head
6
}
7
// 头部变化所以使用dummy node
8
dummy := &ListNode{Val: 0}
9
dummy.Next = head
10
head = dummy
11
// 最开始:0->1->2->3->4->5->nil
12
var pre *ListNode
13
var i = 0
14
for i < m {
15
pre = head
16
head = head.Next
17
i++
18
}
19
// 遍历之后: 1(pre)->2(head)->3->4->5->NULL
20
// i = 1
21
var j = i
22
var next *ListNode
23
// 用于中间节点连接
24
var mid = head
25
for head != nil && j <= n {
26
// 第一次循环: 1 nil<-2 3->4->5->nil
27
temp := head.Next
28
head.Next = next
29
next = head
30
head = temp
31
j++
32
}
33
// 循环需要执行四次
34
// 循环结束:1 nil<-2<-3<-4 5(head)->nil
35
pre.Next = next
36
mid.Next = head
37
return dummy.Next
38
}
Copied!
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
思路:通过 dummy node 链表,连接各个元素
1
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
2
dummy := &ListNode{Val: 0}
3
head := dummy
4
for l1 != nil && l2 != nil {
5
if l1.Val < l2.Val {
6
head.Next = l1
7
l1 = l1.Next
8
} else {
9
head.Next = l2
10
l2 = l2.Next
11
}
12
head = head.Next
13
}
14
// 连接l1 未处理完节点
15
for l1 != nil {
16
head.Next = l1
17
head = head.Next
18
l1 = l1.Next
19
}
20
// 连接l2 未处理完节点
21
for l2 != nil {
22
head.Next = l2
23
head = head.Next
24
l2 = l2.Next
25
}
26
return dummy.Next
27
}
Copied!

​partition-list​

给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。
思路:将大于 x 的节点,放到另外一个链表,最后连接这两个链表
1
func partition(head *ListNode, x int) *ListNode {
2
// 思路:将大于x的节点,放到另外一个链表,最后连接这两个链表
3
// check
4
if head == nil {
5
return head
6
}
7
headDummy := &ListNode{Val: 0}
8
tailDummy := &ListNode{Val: 0}
9
tail := tailDummy
10
headDummy.Next = head
11
head = headDummy
12
for head.Next != nil {
13
if head.Next.Val < x {
14
head = head.Next
15
} else {
16
// 移除<x节点
17
t := head.Next
18
head.Next = head.Next.Next
19
// 放到另外一个链表
20
tail.Next = t
21
tail = tail.Next
22
}
23
}
24
// 拼接两个链表
25
tail.Next = nil
26
head.Next = tailDummy.Next
27
return headDummy.Next
28
}
Copied!
哑巴节点使用场景
当头节点不确定的时候,使用哑巴节点

​sort-list​

在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。
思路:归并排序,找中点和合并操作
1
func sortList(head *ListNode) *ListNode {
2
// 思路:归并排序,找中点和合并操作
3
return mergeSort(head)
4
}
5
func findMiddle(head *ListNode) *ListNode {
6
// 1->2->3->4->5
7
slow := head
8
fast := head.Next
9
// 快指针先为nil
10
for fast !=nil && fast.Next != nil {
11
fast = fast.Next.Next
12
slow = slow.Next
13
}
14
return slow
15
}
16
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
17
dummy := &ListNode{Val: 0}
18
head := dummy
19
for l1 != nil && l2 != nil {
20
if l1.Val < l2.Val {
21
head.Next = l1
22
l1 = l1.Next
23
} else {
24
head.Next = l2
25
l2 = l2.Next
26
}
27
head = head.Next
28
}
29
// 连接l1 未处理完节点
30
for l1 != nil {
31
head.Next = l1
32
head = head.Next
33
l1 = l1.Next
34
}
35
// 连接l2 未处理完节点
36
for l2 != nil {
37
head.Next = l2
38
head = head.Next
39
l2 = l2.Next
40
}
41
return dummy.Next
42
}
43
func mergeSort(head *ListNode) *ListNode {
44
// 如果只有一个节点 直接就返回这个节点
45
if head == nil || head.Next == nil{
46
return head
47
}
48
// find middle
49
middle := findMiddle(head)
50
// 断开中间节点
51
tail := middle.Next
52
middle.Next = nil
53
left := mergeSort(head)
54
right := mergeSort(tail)
55
result := mergeTwoLists(left, right)
56
return result
57
}
Copied!
注意点
  • 快慢指针 判断 fast 及 fast.Next 是否为 nil 值
  • 递归 mergeSort 需要断开中间节点
  • 递归返回条件为 head 为 nil 或者 head.Next 为 nil

​reorder-list​

给定一个单链表 L:L→L→…→L__n→L 将其重新排列后变为: L→L__n→L→L__n→L→L__n→…
思路:找到中点断开,翻转后面部分,然后合并前后两个链表
1
func reorderList(head *ListNode) {
2
// 思路:找到中点断开,翻转后面部分,然后合并前后两个链表
3
if head == nil {
4
return
5
}
6
mid := findMiddle(head)
7
tail := reverseList(mid.Next)
8
mid.Next = nil
9
head = mergeTwoLists(head, tail)
10
}
11
func findMiddle(head *ListNode) *ListNode {
12
fast := head.Next
13
slow := head
14
for fast != nil && fast.Next != nil {
15
fast = fast.Next.Next
16
slow = slow.Next
17
}
18
return slow
19
}
20
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
21
dummy := &ListNode{Val: 0}
22
head := dummy
23
toggle := true
24
for l1 != nil && l2 != nil {
25
// 节点切换
26
if toggle {
27
head.Next = l1
28
l1 = l1.Next
29
} else {
30
head.Next = l2
31
l2 = l2.Next
32
}
33
toggle = !toggle
34
head = head.Next
35
}
36
// 连接l1 未处理完节点
37
for l1 != nil {
38
head.Next = l1
39
head = head.Next
40
l1 = l1.Next
41
}
42
// 连接l2 未处理完节点
43
for l2 != nil {
44
head.Next = l2
45
head = head.Next
46
l2 = l2.Next
47
}
48
return dummy.Next
49
}
50
func reverseList(head *ListNode) *ListNode {
51
var prev *ListNode
52
for head != nil {
53
// 保存当前head.Next节点,防止重新赋值后被覆盖
54
// 一轮之后状态:nil<-1 2->3->4
55
// prev head
56
temp := head.Next
57
head.Next = prev
58
// pre 移动
59
prev = head
60
// head 移动
61
head = temp
62
}
63
return prev
64
}
Copied!

​linked-list-cycle​

给定一个链表,判断链表中是否有环。
思路:快慢指针,快慢指针相同则有环,证明:如果有环每走一步快慢指针距离会减 1
​
1
func hasCycle(head *ListNode) bool {
2
// 思路:快慢指针 快慢指针相同则有环,证明:如果有环每走一步快慢指针距离会减1
3
if head == nil {
4
return false
5
}
6
fast := head.Next
7
slow := head
8
for fast != nil && fast.Next != nil {
9
// 比较指针是否相等(不要使用val比较!)
10
if fast == slow {
11
return true
12
}
13
fast = fast.Next.Next
14
slow = slow.Next
15
}
16
return false
17
}
Copied!
给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
思路:快慢指针,快慢相遇之后,慢指针回到头,快慢指针步调一致一起移动,相遇点即为入环点
​
1
func detectCycle(head *ListNode) *ListNode {
2
// 思路:快慢指针,快慢相遇之后,慢指针回到头,快慢指针步调一致一起移动,相遇点即为入环点
3
if head == nil {
4
return head
5
}
6
fast := head.Next
7
slow := head
8
​
9
for fast != nil && fast.Next != nil {
10
if fast == slow {
11
// 慢指针重新从头开始移动,快指针从第一次相交点下一个节点开始移动
12
fast = head
13
slow = slow.Next // 注意
14
// 比较指针对象(不要比对指针Val值)
15
for fast != slow {
16
fast = fast.Next
17
slow = slow.Next
18
}
19
return slow
20
}
21
fast = fast.Next.Next
22
slow = slow.Next
23
}
24
return nil
25
}
Copied!
坑点
  • 指针比较时直接比较对象,不要用值比较,链表中有可能存在重复值情况
  • 第一次相交后,快指针需要从下一个节点开始和头指针一起匀速移动
另外一种方式是 fast=head,slow=head
1
func detectCycle(head *ListNode) *ListNode {
2
// 思路:快慢指针,快慢相遇之后,其中一个指针回到头,快慢指针步调一致一起移动,相遇点即为入环点
3
// nb+a=2nb+a
4
if head == nil {
5
return head
6
}
7
fast := head
8
slow := head
9
​
10
for fast != nil && fast.Next != nil {
11
fast = fast.Next.Next
12
slow = slow.Next
13
if fast == slow {
14
// 指针重新从头开始移动
15
fast = head
16
for fast != slow {
17
fast = fast.Next
18
slow = slow.Next
19
}
20
return slow
21
}
22
}
23
return nil
24
}
Copied!
这两种方式不同点在于,一般用 fast=head.Next 较多,因为这样可以知道中点的上一个节点,可以用来删除等操作。
  • fast 如果初始化为 head.Next 则中点在 slow.Next
  • fast 初始化为 head,则中点在 slow
请判断一个链表是否为回文链表。
1
func isPalindrome(head *ListNode) bool {
2
// 1 2 nil
3
// 1 2 1 nil
4
// 1 2 2 1 nil
5
if head==nil{
6
return true
7
}
8
slow:=head
9
// fast如果初始化为head.Next则中点在slow.Next
10
// fast初始化为head,则中点在slow
11
fast:=head.Next
12
for fast!=nil&&fast.Next!=nil{
13
fast=fast.Next.Next
14
slow=slow.Next
15
}
16
​
17
tail:=reverse(slow.Next)
18
// 断开两个链表(需要用到中点前一个节点)
19
slow.Next=nil
20
for head!=nil&&tail!=nil{
21
if head.Val!=tail.Val{
22
return false
23
}
24
head=head.Next
25
tail=tail.Next
26
}
27
return true
28
​
29
}
30
​
31
func reverse(head *ListNode)*ListNode{
32
// 1->2->3
33
if head==nil{
34
return head
35
}
36
var prev *ListNode
37
for head!=nil{
38
t:=head.Next
39
head.Next=prev
40
prev=head
41
head=t
42
}
43
return prev
44
}
Copied!
给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。 要求返回这个链表的 深拷贝。
思路:1、hash 表存储指针,2、复制节点跟在原节点后面
1
func copyRandomList(head *Node) *Node {
2
if head == nil {
3
return head
4
}
5
// 复制节点,紧挨到到后面
6
// 1->2->3 ==> 1->1'->2->2'->3->3'
7
cur := head
8
for cur != nil {
9
clone := &Node{Val: cur.Val, Next: cur.Next}
10
temp := cur.Next
11
cur.Next = clone
12
cur = temp
13
}
14
// 处理random指针
15
cur = head
16
for cur != nil {
17
if cur.Random != nil {
18
cur.Next.Random = cur.Random.Next
19
}
20
cur = cur.Next.Next
21
}
22
// 分离两个链表
23
cur = head
24
cloneHead := cur.Next
25
for cur != nil && cur.Next != nil {
26
temp := cur.Next
27
cur.Next = cur.Next.Next
28
cur = temp
29
}
30
// 原始链表头:head 1->2->3
31
// 克隆的链表头:cloneHead 1'->2'->3'
32
return cloneHead
33
}
Copied!

总结

链表必须要掌握的一些点,通过下面练习题,基本大部分的链表类的题目都是手到擒来~
  • null/nil 异常处理
  • dummy node 哑巴节点
  • 快慢指针
  • 插入一个节点到排序链表
  • 从一个链表中移除一个节点
  • 翻转链表
  • 合并两个链表
  • 找到链表的中间节点

练习

最近更新 1yr ago