我的成长笔记

Appearance

链表与虚拟头结点 ​

链表最容易卡住的地方，通常不是“节点怎么定义”，而是指针到底应该站在哪里，以及修改前后谁还指向谁。虚拟头结点（dummy head）正是用来降低这种思维负担的技巧：它不存放业务数据，只负责让链表的边界变得统一。

配合阅读：链表与虚拟头结点交互式图解

1. 链表到底是什么 ​

一个单链表节点包含两部分：数据 val 和指向下一个节点的指针 next。

go
type ListNode struct {
	Val  int
	Next *ListNode
}

假设有 1 → 2 → 3：

text
head
  │
  ▼
[1 | next] → [2 | next] → [3 | nil]

head 只保存第一个节点的地址。最后一个节点的 next == nil，这就是链表结束的标志。链表节点在内存中不要求连续，因此插入和删除不需要搬动后面的元素；代价是不能像数组那样通过下标 O(1) 访问第 k 个元素。

操作数组单链表
按下标访问O(1)O(n)
头部插入/删除O(n)O(1)
已知前驱后的插入/删除O(n)O(1)
搜索一个值O(n)O(n)

这里的“链表插入是 O(1)”有一个前提：你已经拿到了插入位置的前驱节点。如果还要先走到那个位置，寻找过程仍然是 O(n)。

2. 为什么头结点最容易写错 ​

普通链表的第一个节点同时承担了两种角色：它是一个真实数据节点，也是整条链的入口。删除第一个节点时，入口本身要改变：

go
head = head.Next

而删除中间节点只需要改前驱：

go
prev.Next = prev.Next.Next

于是同一个“删除节点”问题出现了两套代码，还必须额外处理空链表、只有一个节点、删除头节点等边界情况。很多 bug 都来自这里：循环逻辑本身是对的，却忘了更新 head。

3. 虚拟头结点：一个不属于数据的哨兵 ​

虚拟头结点是一个额外创建的节点，放在真实头结点之前：

text
dummy → 1 → 2 → 3 → nil

它的值没有意义，重要的是它始终存在。真实链表的头结点变成 dummy.Next，而所有真实节点都有一个前驱：

go
dummy := &ListNode{Next: head}

现在删除第一个真实节点，不需要特殊处理：dummy 就是它的前驱。

go
dummy.Next = dummy.Next.Next
head = dummy.Next

可以把它理解成在链表入口前修了一小段“缓冲路”。它不改变数据，只让“第一个节点”和“中间节点”拥有相同的结构。

4. 最重要的操作模板 ​

4.1 删除指定值的节点 ​

go
func removeElements(head *ListNode, target int) *ListNode {
	dummy := &ListNode{Next: head}
	cur := dummy

	for cur.Next != nil {
		if cur.Next.Val == target {
			cur.Next = cur.Next.Next
		} else {
			cur = cur.Next
		}
	}
	return dummy.Next
}

注意循环条件是 cur.Next != nil，因为我们要检查并删除的是 cur.Next，而不是 cur。删除后不要移动 cur：新的 cur.Next 还没有检查，连续出现 2 → 2 时才能一次删干净。

4.2 头部插入 ​

go
node := &ListNode{Val: 0, Next: dummy.Next}
dummy.Next = node

先让新节点接上旧链，再让 dummy.Next 指向新节点。改变指针时，通常遵循“先保存/连接后继，再改入口”的顺序，避免把链断掉。

4.3 反转链表 ​

反转不依赖虚拟头结点，但最能体现指针操作的核心：每一步都要先保存 cur.Next。

go
func reverseList(head *ListNode) *ListNode {
	var prev *ListNode
	cur := head
	for cur != nil {
		next := cur.Next // 保存还未处理的部分
		cur.Next = prev  // 箭头反向
		prev = cur
		cur = next
	}
	return prev
}

循环不变量是：prev 指向已经反转好的前缀，cur 指向尚未处理的部分。每轮只完成一个节点的归属变化。

4.4 合并两个有序链表 ​

这里虚拟头结点尤其自然：新链表的第一个节点也由同一套“把节点接到尾部”的逻辑完成。

go
func mergeTwoLists(a, b *ListNode) *ListNode {
	dummy := &ListNode{}
	tail := dummy
	for a != nil && b != nil {
		if a.Val <= b.Val {
			tail.Next, a = a, a.Next
		} else {
			tail.Next, b = b, b.Next
		}
		tail = tail.Next
	}
	if a != nil {
		tail.Next = a
	} else {
		tail.Next = b
	}
	return dummy.Next
}

5. 什么时候应该使用虚拟头结点 ​

看到下面任意一种信号，就可以优先考虑它：

  • 需要删除、插入、重排，且操作可能发生在第一个真实节点处；
  • 循环中要频繁写 prev.Next，但 prev 可能是“头结点的前一个位置”；
  • 合并多个链表，需要不断维护结果链表的尾指针；
  • 代码里出现大量 if head == nil、if head.Val == target 之类的头部特判。

它不是必须的。只读遍历、反转链表、快慢指针找中点等场景，用普通 head 更直观。虚拟头结点的目标也不是让复杂度变低，而是把边界条件纳入统一的结构。

6. 高频题型背后的统一思路 ​

找倒数第 k 个节点 ​

让 fast 先走 k 步，再让 fast、slow 同步走。两者保持固定距离，fast 到尾部时 slow 就在目标位置。

判断环 ​

快指针一次两步，慢指针一次一步。若相遇则有环；若 fast 或 fast.Next 为空则无环。判断环入口时，相遇后把一个指针放回头部，两者每次一步再次相遇的位置就是入口。

删除倒数第 k 个节点 ​

这正是虚拟头结点的典型题：让 fast 比 slow 先走 k + 1 步，最终 slow 停在待删节点的前驱，直接执行 slow.Next = slow.Next.Next，删除头节点也无需特判。

两两交换节点 ​

把 prev 放在每一对节点之前。交换 a、b 时只改三条边：

text
prev → a → b → next
prev → b → a → next

dummy 负责第一对节点之前的 prev，之后每次把 prev 移到交换完成的 a。

7. 调试链表的三个习惯 ​

  1. 每次改指针前画图：至少画出 prev、cur、next 和目标节点。
  2. 检查入口和终点：返回值通常是 dummy.Next 或新的头指针；尾节点最终必须指向 nil。
  3. 用小样例覆盖边界：空链表、单节点、删除头部、连续重复值、k 等于长度、k 大于长度。

如果链表“遍历不结束”，优先检查是否误把某个 Next 指回了已经访问过的节点；如果节点“凭空消失”，优先检查是否在保存后继节点之前覆盖了 Next。

8. 一句话记忆 ​

链表题的本质是维护连接关系；虚拟头结点只是给第一个真实节点补上一个稳定的前驱。写题时先确定“我需要站在待操作节点，还是它的前驱”，再按照“保存后继、修改连接、移动指针”的顺序执行，绝大多数边界 bug 都会消失。

最后更新时间: