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

【算法】链表一世界观与指针操作——攥住再改、重绑与改对象、哨兵节点摘要链表系列第一篇。从数组转场链表最先撞的不是算法是世界观数组是一个连续的东西链表是一堆独立节点 指针关系——持有头节点不等于持有链表持有的是入口链长在指针网络里。本篇两题三课LC206 反转链表先写了个头插法重建绕过指针操作——功能对但 O(n) 空间被自己注释里指针被移动就丢失后续的诊断打脸已精确诊断出断链风险然后回避了它原地版一行精髓改指针之前先攥住会丢的东西递归版两个精髓——head.Next 不用动反转让它指着的节点自动从头变成尾的头尾互换性质和newHead 从头到尾没被动过一行代码链却越长越长的指针网络之谜LC21 合并有序链表哨兵节点 dummy——结构对了特判蒸发的链表版选头样板 7 行 → 0 行、循环四分支 → 两分支、空链守卫整个蒸发。外加一段语言地基重绑 vs 改对象——换便签各是各的.字段改房子全局可见链表题的一切指针操作都是这两个动作的组合。前置阅读双指针与滑动窗口一框架总纲——三类问题、一个原理与判决书。配套代码仓库按题号分目录https://github.com/a18792721831/studyleetCode【算法】链表一世界观与指针操作——攥住再改、重绑与改对象、哨兵节点【算法】链表一世界观与指针操作——攥住再改、重绑与改对象、哨兵节点摘要1. 世界观链长在指针网络里2. 语言地基重绑 vs 改对象3. 第一课 LC206反转链表三种姿势3.1 头插法正确的答案回避的题3.2 原地版攥住再改3.3 递归版头尾互换 指针网络之谜4. 第二课 LC21哨兵节点 dummy5. 速查表总结参考资料1. 世界观链长在指针网络里数组转链表最先要换的不是算法是脑子。数组是一段连续内存下标天然存在、O(1) 能回头看链表是一堆散落在内存里的节点 Next 指针织成的网络——这个差异派生出链表题的三条公理公理一持有头节点 ≠ 持有链表。头节点只是一张入口门票——“链的内容” 从入口出发顺着 Next 能走到的一切。节点可以共享两条链从交点后手拉手、可以成环网络里绕回起点、可以悬空没有入口指向它的节点等于不存在。公理二没有回头看。Next 单向、下标不存在——想看前一个节点没有。这就是为什么链表题大量使用双指针一个替你记着另一个位置和 dummy替你虚构一个头之前的节点。公理三指针操作不可逆、且瞬时会丢东西。改掉curr.Next的那一刻后半截链表从 curr 的手里逃走——除非提前攥住它。这是链表题第一死因解药就一行改指针之前先攥住会丢的东西next : curr.Next。2. 语言地基重绑 vs 改对象写链表代码前必须分清两个动作混了就是灾难slowslow.Next// ① 重绑变量换自己便签上的门牌 —— 别的变量看不见slow.Nextprev// ② 修改对象走进门牌那栋房子改结构 —— 所有指向它的变量都看得见我在 LC160 时产生过一个经典困惑“head 和 slow 指向同一个节点改了 slowhead 会不会跟着变”——不会。变量是便签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 头插法正确的答案回避的题我的第一版varnewHead*ListNodeforhead!nil{newHeadListNode{Val:head.Val,Next:newHead}// 每 new 一个新节点headhead.Next}功能全对但这是头插法重建——O(n) 空间 new 了整条新链一次指针操作都没碰。讽刺的是我注释里写着当 head.next 的指针被移动就丢失后续的了——已经精确诊断出了断链风险然后用 new 新节点回避了它而不是解决它。LeetCode 会 accept它只看输出面试官会追问能原地吗——而原地版才是这题的教学目标。头插法本身是正经技巧后面某些题真有用但用它回避指针操作恐惧还在只是没面对。3.2 原地版攥住再改funcreverseList(head*ListNode)*ListNode{varprev*ListNode// 已反转段的头初始空curr:headforcurr!nil{next:curr.Next// ① 先攥住后半截 —— 公理三的解药curr.Nextprev// ② 反转指向后半截已在 next 手里敢改了prevcurr// ③ prev 前进currnext// ④ curr 前进}returnprev// curr 走到 nilprev 停在原尾 新头}循环不变量判决书prev 左边含永远是已反转好的段curr 右边永远是未动的段——①②③④每步之后性质保持。正确性靠不变量效率靠单向性每个节点只路过一次。3.3 递归版头尾互换 指针网络之谜递归版的两个精髓一个比一个反直觉精髓一head.Next 不用动它指着的节点在反转中自动从头变成尾。子链表2→3反转成3→2后头是 3、尾是 2——而1.Next从下沉到回卷一直指着 2 没动过含义却从子链表的头变成了子链表的尾。所以接线的位置不用找head.Next就是尾head.Next.Next head把原 head 挂到尾巴上funcreverseList(head*ListNode)*ListNode{ifheadnil||head.Nextnil{returnhead}newHead:reverseList(head.Next)// 相信它能反转后面拿回新头head.Next.Nexthead// head.Next 已从头变尾——接在尾上head.Nextnil// head 成为新尾不断就是双向环returnnewHead}我第一次写的递归版栽在这两行上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 版funcmergeTwoLists(list1,list2*ListNode)*ListNode{dummy:ListNode{}// 哨兵站在结果链头【前面】的假节点tail:dummy// tail 永远指向结果链的尾此刻尾dummyforlist1!nillist2!nil{iflist1.Vallist2.Val{tail.Nextlist1 list1list1.Next}else{tail.Nextlist2 list2list2.Next}tailtail.Next}iflist1!nil{tail.Nextlist1}// 剩余段整段接iflist2!nil{tail.Nextlist2}returndummy.Next// 真头 假节点的下一个}清点收益选头样板 7→0 行、循环四分支→两分支两个整段接、空链守卫整个蒸发list1 为 nil 时循环不进、直接整段接、返回 dummy.Next——全 nil 也正确。dummy 的本质一句话在头还不存在的位置预先放一个假节点让第一个节点永远不再是特例——每个真节点含第一个都执行同一动作接到 tail 后面。假节点挡在前面吃掉所有边界return dummy.Next交出真头。这是结构对了特判蒸发的链表版——和双指针系列里li1消灭 idx 特判LC15、“lr循环覆盖单元素”LC33是同一条规律在三个家族的化身。顺带一提这个技巧我其实天天在用——每道链表题的测试代码里build函数就是 dummy 写法没有它建链函数也得写头特判。工具一直都在只是做题时没想到主函数也该用。5. 速查表问题判据/口诀出处改指针之前先攥住会丢的东西next : curr.Next——不攥就是断链LC206重绑 vs 改对象换便签各是各的.字段改房子全局可见LC160 困惑 / 全系列指针联动疑问用调试器看地址别概念争论LC142 误诊事件递归反转head.Next 反转后自动从子链表头变尾——接线写在尾巴上head.Next.Next headLC206递归的世界观返回的头节点 入口门票链长在指针网络里回卷每层往尾部接一个节点LC206头节点特判用 dummy让第一个节点不再是特例return dummy.NextLC21/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 版权协议转载请附上原文出处链接和本声明。