这两天在复习链表，我一想，这链表这么简单的东西还有什么复习的，简单过一遍不就行了

然而马上打脸，有些题目我居然还写不出来（乐

理论基础

先来点你肯定知道的东西，简单过一遍

是什么

image-20230602下午123049988

如图所示，链表是一种链式结构，以最简单的单链表为例：

1
2
3
4
type ListNode struct {
    Val  int
    Next *ListNode
}

也就是头节点指向下一个节点，然后下一个节点再指向下一个节点，如果是尾节点就指向 NULL （或者说是 Golang 里的 nil ）

基本操作

删除节点

image-20230602下午125326797

让前面节点认为它的后面是后面的节点

删除的节点让 GC 自动回收掉即可

添加节点

image-20230602下午10229378

让新节点指向后面节点，让前面节点指向新节点

链表的几种变体

有头链表

image-20230602下午13821938

减少对头节点的特殊处理

双向链表

image-20230602下午14306969

可以方便地找到前驱节点

对于一个有序链表，双向链表的按值查询效率要比单链表高一些。因为我们可以记录上次查找的位置p，每一次查询时，根据要查找的值与p的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。

循环链表

image-20230602下午14652973

能解决约瑟夫问题

有头双向循环链表

buff 叠满，请见 【有头双向循环链表之美，这个数据结构简单又优雅，学会了不亏】

链表 vs 数组

插入删除 随机访问
数组 O(n)O(n) O(1)O(1)
链表 O(1)O(1) O(n)O(n)

必知必会的题目

707. 设计链表

实现一个链表，这里就以带头单链表为例

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
type MyLinkedList struct {
	head *ListNode
	size int
}

type ListNode struct {
	val  int
	next *ListNode
}

// Constructor 初始化 MyLinkedList 对象
func Constructor() MyLinkedList {
	dummyHead := &ListNode{}
	return MyLinkedList{
		head: dummyHead,
		size: 0,
	}
}

// Get 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1
func (this *MyLinkedList) Get(index int) int {
	if index < 0 || index >= this.size {
		return -1
	}
	cur := this.head.next
	for i := 0; i < index; i++ {
		cur = cur.next
	}
	return cur.val
}

// AddAtHead 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点
func (this *MyLinkedList) AddAtHead(val int) {
	newNode := &ListNode{val: val}
	newNode.next = this.head.next
	this.head.next = newNode
	this.size++
}

// AddAtTail 将一个值为 val 的节点追加到链表中作为链表的最后一个元素
func (this *MyLinkedList) AddAtTail(val int) {
	newNode := &ListNode{val: val}
	cur := this.head
	for cur.next != nil {
		cur = cur.next
	}
	cur.next = newNode
	this.size++
}

// AddAtIndex 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。
// 如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。
// 如果 index 比长度更大，该节点将 不会插入 到链表中
func (this *MyLinkedList) AddAtIndex(index int, val int) {
	if index < 0 || index > this.size {
		return
	}
	if index == this.size {
		this.AddAtTail(val)
		return
	}
	cur := this.head
	for i := 0; i < index; i++ {
		cur = cur.next
	}
	newNode := &ListNode{val: val}
	newNode.next = cur.next
	cur.next = newNode
	this.size++
}

// DeleteAtIndex 如果下标有效，则删除链表中下标为 index 的节点
func (this *MyLinkedList) DeleteAtIndex(index int) {
	if index < 0 || index >= this.size {
		return
	}
	cur := this.head
	for i := 0; i < index; i++ {
		cur = cur.next
	}
	cur.next = cur.next.next
	this.size--
}

206. 反转链表

字面意思，翻转一个链表

操作过程如下：

  1. 初始化当前节点为头节点
  2. 暂存下一个节点
  3. 将当前节点指向前一个节点
  4. 前驱节点后移
  5. 当前节点后移
  6. 重复 1-4，只到当前节点为 NULL ，输出前驱结点为新的头结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func reverseList(head *ListNode) *ListNode {
	// 定义前驱节点、当前节点、后继节点
	var prev *ListNode = nil
	var next *ListNode = nil
	var curr *ListNode = head

	// 遍历链表
	for curr != nil {
		// 保存下一个节点
		next = curr.Next
		// 当前节点指向前驱节点
		curr.Next = prev
		// 前驱节点后移
		prev = curr
		// 当前节点后移
		curr = next
	}

	// 返回前驱节点
	return prev
}

我一开始也不是很懂，所以我画了个图一步一步来，图画出来我就懂了

image-20230601下午103709377

类似地，还有一个递归的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func reverseList(head *ListNode) *ListNode {
	// 如果链表为空或者只有一个节点，直接返回原链表
	if head == nil || head.Next == nil {
		return head
	}
	// 递归反转除头节点外的子链表
	p := reverseList(head.Next)
	// 将当前节点的下一个节点指向当前节点，实现反转
	head.Next.Next = head
	// 将当前节点的下一个节点置空，断开原链表中的连接
	head.Next = nil
	// 返回反转后的链表的头节点
	return p
}

876. 链表的中间结点

使用快慢指针（ i 走一步， j 走两步）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func middleNode(head *ListNode) *ListNode {
	// 定义快慢指针
	var fast *ListNode = head
	var slow *ListNode = head

	// 快指针走两步，慢指针走一步
	for fast != nil && fast.Next != nil {
		fast = fast.Next.Next
		slow = slow.Next
	}

	// 返回慢指针
	return slow
}

21. 合并两个有序链表

第一版以为不能修改他给出的链表，每次都 new 一个节点，结果 TLE 了，好尴尬

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
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	// 创建一个哨兵节点作为新链表的头部
    dummy := &ListNode{}
	curr := dummy

    // 遍历两个链表，比较节点的值，将较小值的节点添加到新链表中
	for list1 != nil && list2 != nil {
		if list1.Val > list2.Val {
			curr.Next = list2
			list2 = list2.Next
			curr = curr.Next
		} else {
			curr.Next = list1
			list1 = list1.Next
			curr = curr.Next
		}
	}

    // 如果其中一个链表已经遍历完了，直接将另一个链表剩余部分添加到新链表中
	if list1 != nil {
		curr.Next = list1
	}

	if list2 != nil {
		curr.Next = list2
	}

	return dummy.Next
}

234. 回文链表

用快慢指针找到中点，然后反转后半部分，从开始和中间向后进行比较

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
func isPalindrome(head *ListNode) bool {
	// 定义快慢指针
	var slow *ListNode = head
	var fast *ListNode = head

	// 快慢指针走到中间节点
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}

	// 如果fast不为空，说明链表长度为奇数，slow还要再前进一步
	if fast != nil {
		slow = slow.Next
	}

  // 反转后半部分链表（见上面的实现）
	slow = reverseList(slow)

	// 比较前后两部分链表
	for slow != nil {
		if slow.Val != head.Val {
			return false
		}
		slow = slow.Next
		head = head.Next
	}

	return true
}

19. 删除链表的倒数第 N 个结点

还是双指针，i j 初始为 head，然后 j 先走 N 步，然后一起往后走

这个东西有点坑，一开始没弄哨兵节点，删除的操作总是有问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	dummy := &ListNode{Next: head}
	slow, fast := dummy, dummy

	for i := 0; i < n; i++ {
		fast = fast.Next
	}

	for fast.Next != nil {
		slow = slow.Next
		fast = fast.Next
	}

	slow.Next = slow.Next.Next

	return dummy.Next
}

141. 环形链表

判断一个链表中有没有环

还是快慢指针，如果快指针能追上慢指针就肯定有环了

1
2
3
4
5
6
7
8
9
10
11
12
13
func hasCycle(head *ListNode) bool {
	fast := head
	slow := head

	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if fast == slow {
			return true
		}
	}
	return false
}

当然你也可以用更直白的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func hasCycle(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return false
	}
	for head != nil {
		if head.Val == 123512151 {
			return true
		} else {
			head.Val = 123512151
		}
		head = head.Next
	}
	return false
}

142. 环形链表 II

这个题目需要在判断出有环后能找到环的起点

推理过程请见 代码随想录 👀

反正结论就是：当快慢指针相遇时，让其中一个回到头结点，然后同速前进，再次相遇即为环开始的点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func detectCycle(head *ListNode) *ListNode {
	fast := head
	slow := head

	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if fast == slow {
			fast = head
			for fast != slow {
				fast = fast.Next
				slow = slow.Next
			}
			return fast
		}
	}
	return nil
}

理论上你也可以使用更直白的方法，但是题目要求不能修改链表

面试题 02.07. 链表相交

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
func getIntersectionNode(headA, headB *ListNode) *ListNode {
	lengthA := getLength(headA)
	lengthB := getLength(headB)
	var fast, slow *ListNode
	step := 0
	if lengthA > lengthB {
		step = lengthA - lengthB
		fast, slow = headA, headB
	} else {
		step = lengthB - lengthA
		fast, slow = headB, headA
	}
	for i := 0; i < step; i++ {
		fast = fast.Next
	}
	//遍历两个链表，相同则跳出
	for fast != slow {
		fast = fast.Next
		slow = slow.Next
	}
	return fast
}

func getLength(head *ListNode) (length int) {
	for ; head != nil; head = head.Next {
		length++
	}
	return
}