【算法】链表（一）：世界观与指针操作——攥住再改、重绑与改对象、哨兵节点

文章信息

• 原文链接：https://jiayq.blog.csdn.net/article/details/164821613
• 发布时间：2026-09-12 09:00:00
• 标签：#Golang, #算法, ##开学季·九月创作之星博客挑战赛, ##数据结构, ##算法讲解

---

【算法】链表（一）：世界观与指针操作——攥住再改、重绑与改对象、哨兵节点

摘要

链表系列第一篇。从数组转场链表，最先撞的不是算法，是世界观 ：数组是一个连续的”东西”，链表是一堆独立节点 + 指针关系 ——持有头节点不等于持有链表，持有的是入口，链长在指针网络里。本篇两题三课：LC206 反转链表 （先写了个”头插法重建”绕过指针操作——功能对但 O(n) 空间，被自己注释里”指针被移动就丢失后续”的诊断打脸：已精确诊断出断链风险，然后回避了它 ；原地版一行精髓”改指针之前，先攥住会丢的东西 “；递归版两个精髓——”head.Next 不用动，反转让它指着的节点自动从头变成尾 “的头尾互换性质，和”newHead 从头到尾没被动过一行代码，链却越长越长”的指针网络之谜）；LC21 合并有序链表 （哨兵节点 dummy——”结构对了特判蒸发”的链表版：选头样板 7 行 → 0 行、循环四分支 → 两分支、空链守卫整个蒸发）。外加一段语言地基：重绑 vs 改对象 ——= 换便签（各是各的），.字段= 改房子（全局可见），链表题的一切指针操作都是这两个动作的组合。

前置阅读：双指针与滑动窗口（一）：框架总纲——三类问题、一个原理与判决书。配套代码仓库（按题号分目录）：https://github.com/a18792721831/studyleetCode

1. 世界观：链长在指针网络里

数组转链表，最先要换的不是算法是脑子。数组是一段连续内存，下标天然存在、O(1) 能回头看；链表是一堆散落在内存里的节点 + Next 指针织成的网络 ——这个差异派生出链表题的三条公理：

公理一：持有头节点 ≠ 持有链表。 头节点只是一张入口门票 ——“链的内容” = 从入口出发顺着 Next 能走到的一切。节点可以共享（两条链从交点后手拉手）、可以成环（网络里绕回起点）、可以悬空（没有入口指向它的节点等于不存在）。

公理二：没有”回头看”。 Next 单向、下标不存在——想看前一个节点？没有。这就是为什么链表题大量使用双指针（一个替你记着另一个位置）和 dummy（替你虚构一个”头之前的节点”）。

公理三：指针操作不可逆、且瞬时会丢东西。 改掉 curr.Next 的那一刻，后半截链表从 curr 的手里逃走 ——除非提前攥住它。这是链表题第一死因，解药就一行：改指针之前，先攥住会丢的东西 （next := curr.Next）。

2. 语言地基：重绑 vs 改对象

写链表代码前必须分清两个动作，混了就是灾难：

slow = slow.Next     // ① 重绑变量：换自己便签上的门牌 —— 别的变量看不见
slow.Next = prev     // ② 修改对象：走进门牌那栋房子改结构 —— 所有指向它的变量都看得见

我在 LC160 时产生过一个经典困惑：“head 和 slow 指向同一个节点，改了 slow，head 会不会跟着变？”——不会 。变量是便签，slow := head 只是抄了一份门牌号；slow = slow.Next 是擦掉自己便签上的号换个新的，head 的便签纹丝不动。只有 ②（.字段=）才”联动”——因为那次是真的去了房子里动了东西。

一句话钉死：= 改的是便签，.字段 = 改的是房子。便签各是各的，房子是共享的。

最有说服力的证据是我自己跑对的代码：hasCycle 里 slow = slow.Next 若真会带动 fast，快慢指针早永远同步了，速度差根本无从谈起。怀疑假设，就用调试器看实际地址 ——这比概念争论快一万倍（LC142 我用断点看到三个变量同地址，当场揭穿一个误诊）。

3. 第一课 LC206：反转链表，三种姿势

1→2→3→4→5 反转为 5→4→3→2→1。

3.1 头插法：正确的答案，回避的题

我的第一版：

var newHead *ListNode
for head != nil {
    newHead = &ListNode{Val: head.Val, Next: newHead}   // 每 new 一个新节点
    head = head.Next
}

功能全对，但这是头插法重建 ——O(n) 空间 new 了整条新链，一次指针操作都没碰 。讽刺的是我注释里写着”当 head.next 的指针被移动，就丢失后续的了”——已经精确诊断出了断链风险，然后用 new 新节点回避了它，而不是解决它 。LeetCode 会 accept（它只看输出），面试官会追问”能原地吗”——而原地版才是这题的教学目标。头插法本身是正经技巧（后面某些题真有用），但用它回避指针操作，恐惧还在，只是没面对。

3.2 原地版：攥住再改

func reverseList(head *ListNode) *ListNode {
	var prev *ListNode          // 已反转段的头（初始空）
	curr := head
	for curr != nil {
		next := curr.Next       // ① 先攥住后半截 —— 公理三的解药
		curr.Next = prev        // ② 反转指向（后半截已在 next 手里，敢改了）
		prev = curr             // ③ prev 前进
		curr = next             // ④ curr 前进
	}
	return prev                 // curr 走到 nil，prev 停在原尾 = 新头
}

循环不变量（判决书）：prev 左边（含）永远是已反转好的段，curr 右边永远是未动的段 ——①②③④每步之后性质保持。正确性靠不变量，效率靠单向性（每个节点只路过一次）。

3.3 递归版：头尾互换 + 指针网络之谜

递归版的两个精髓，一个比一个反直觉：

精髓一：head.Next 不用动，它指着的节点在反转中自动”从头变成尾”。 子链表 2→3 反转成 3→2 后，头是 3、尾是 2——而 1.Next 从下沉到回卷一直指着 2 没动过 ，含义却从”子链表的头”变成了”子链表的尾”。所以接线的位置不用找：head.Next 就是尾，head.Next.Next = head 把原 head 挂到尾巴上：

func reverseList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	newHead := reverseList(head.Next)   // 相信它能反转后面，拿回新头
	head.Next.Next = head               // head.Next 已从"头"变"尾"——接在尾上
	head.Next = nil                     // head 成为新尾（不断就是双向环）
	return newHead
}

我第一次写的递归版栽在这两行上：head.Next = prev（接到了新头 后面而不是新尾 后面），结果 1→2→3 反转成 3→1 加一个环 1→2→3→1——实测当场抓包。原 head 是反转后的最后一个节点，当然挂到尾巴上——挂到头上，旧线没人清理，环就诞生了。

精髓二：newHead 为什么是完整的链？ 从触底那一刻起，newHead 没有被动过一行代码——每层只是 return newHead 原样上传。那 4 后面的 3、2、1 是怎么”长”出来的？它们不是长在 newHead 身上，是长在指针网络里 ：

触底后：  从 4 出发能走到：4
第 3 层后：从 4 出发能走到：4→3
第 2 层后：从 4 出发能走到：4→3→2
第 1 层后：从 4 出发能走到：4→3→2→1   ← "完整的链"诞生

newHead 这个变量从头到尾没变，变的只是”从它出发能走到的范围” ——每层回卷往网络的尾部（被上一层清空的 nil 槽位）接一个节点。断→接→断→接，像接力棒。这就是公理一的实战形态。

4. 第二课 LC21：哨兵节点 dummy

合并两个有序链表。[1,2,4] + [1,3,4] → [1,1,2,3,4,4]。

我的第一版（无 dummy）有两处痛点，都是 dummy 的靶子：

痛点一：开头 7 行”选头”样板。 res = 较小头; 该链前进; index = res——存在理由只有一个：结果链的头还不存在，第一个被接上的节点没有”前任”可接 ，只能特判。

痛点二：循环里两个”逐节点接”分支。 list1 空了以后逐个接 list2 的节点——但剩余段本来就有序 ，一条 tail.Next = list2 能整段接上，逐个比较是白干（判决书：一链空 ⟹ 另一链剩余段有序 ⟹ 无需再比）。

dummy 版：

func mergeTwoLists(list1, list2 *ListNode) *ListNode {
	dummy := &ListNode{}          // 哨兵：站在结果链头【前面】的假节点
	tail := dummy                  // tail 永远指向结果链的尾（此刻尾=dummy）
	for list1 != nil && list2 != nil {
		if list1.Val <= list2.Val {
			tail.Next = list1
			list1 = list1.Next
		} else {
			tail.Next = list2
			list2 = list2.Next
		}
		tail = tail.Next
	}
	if list1 != nil { tail.Next = list1 }   // 剩余段整段接
	if list2 != nil { tail.Next = list2 }
	return dummy.Next              // 真头 = 假节点的下一个
}

清点收益：选头样板 7→0 行、循环四分支→两分支+两个整段接、空链守卫整个蒸发 （list1 为 nil 时循环不进、直接整段接、返回 dummy.Next——全 nil 也正确）。

dummy 的本质一句话：在”头还不存在”的位置预先放一个假节点，让”第一个节点”永远不再是特例 ——每个真节点（含第一个）都执行同一动作”接到 tail 后面”。假节点挡在前面吃掉所有边界，return dummy.Next 交出真头。这是”结构对了特判蒸发”的链表版——和双指针系列里”l=i+1 消灭 idx 特判”（LC15）、“l<=r 循环覆盖单元素”（LC33）是同一条规律在三个家族的化身。

顺带一提：这个技巧我其实天天在用——每道链表题的测试代码里build 函数就是 dummy 写法，没有它建链函数也得写头特判。工具一直都在，只是做题时没想到主函数也该用。

5. 速查表

问题	判据/口诀	出处
改指针之前	先攥住会丢的东西 （next := curr.Next）——不攥就是断链	LC206
重绑 vs 改对象	= 换便签（各是各的）；.字段= 改房子（全局可见）	LC160 困惑 / 全系列
指针联动疑问	用调试器看地址，别概念争论	LC142 误诊事件
递归反转	head.Next 反转后自动”从子链表头变尾”——接线写在尾巴上（head.Next.Next = head）	LC206
递归的世界观	返回的头节点 = 入口门票；链长在指针网络里，回卷每层往尾部接一个节点	LC206
头节点特判	用 dummy：让”第一个节点”不再是特例；return dummy.Next	LC21/LC19
一链耗尽	剩余段有序，整段接 ，不逐个比	LC21
变量命名	名字与语义一致（fast 配快速度）；变量名不换含义	LC141 命名倒置
遇到”功能对但绕过了考点”	问自己：是在解决问题还是在回避问题？空间/时间复杂度是不是偷偷变差了	LC206 头插法

总结

两道基础题，三个层次的收获：

世界观先于算法。 “链长在指针网络里”这一条，解释了递归反转里 newHead 的不动之谜、解释了 LC160 的 nil 会师、也预示了下一篇环和交点的所有操作——链表题的一半错误（Val 比较代替指针比较、以为改 slow 会联动 head）都是拿”连续数组”的直觉套”指针网络”的现实。

回避不是解决。 头插法那版最值得记：诊断出了断链风险，然后用 O(n) 空间绕过去了——恐惧被租金覆盖，但还在 。原地版的一行”先攥住”才是把恐惧变成理解的那一刻。写”正确的答案”和”做对题”不是一回事，尤其当题目考的就是你绕过的那部分。

dummy 是链表题的默认开场。 只要涉及”改链/接链/删链”，先立 dummy 再说——它把头节点从”特例”降级成”普通节点”，让循环体对所有节点一视同仁。结构对了，特判蒸发——这条规律已经在三个算法家族反复验证。

下一篇：链表上的双指针——变速（找环）、异链（找交点）、定距（删倒数第 N），和一份贯穿三题的路程账本。

参考资料

• LeetCode 206. 反转链表
• LeetCode 21. 合并两个有序链表
• LeetCode 160. 相交链表
• 双指针与滑动窗口（一）：框架总纲——三类问题、一个原理与判决书

---

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。