刷题打卡进入第四天节奏对上味了。前三天如果还在折腾数组、二分、双指针热身从今天开始才算真正进入链表操作的手感区24. 两两交换链表中的节点19. 删除链表的倒数第N个节点142. 环形链表 II。这组题在 LeetCode 上都是高频题面试出现概率极高特点是思路不复杂全靠对指针操作的精确掌控——你能在五分钟内想出方案却可能因为一句赋值顺序写错Debug 半小时找不到问题。这篇文章把三道题的完整分析、参考实现和踩坑记录整理出来。不管你是刚开始刷题的新手还是准备跳槽想系统复习一轮算法的人都建议停下来认真过一遍。链表这个东西最忌讳“看懂了等于会了”必须亲手写、亲手调把指针重排的肌肉记忆练出来。1. 这三道链表题究竟在考什么本事1.1 一个共同内核指针的“手术刀”链表和数组最大的区别在哪里数组是连续内存可以按下标随机访问插入删除代价高链表则是一块块零散内存用指针串起来想“插入”或“删除”某个节点本质是改目标前后邻居的指针指向。所以链表题的核心从来不是“遍历得多快”而是“改指针时别把链搞断”。这三道题恰好从三个角度训练这项能力。24 题是纯指针重排要求你在有限几步内完成四个指针的重新连接19 题引入了双指针里的“快慢指针”实际上是一个定长滑块142 题把快慢指针用到极致涉及 Floyd 判圈算法。它们共同指向一个基本功用两个甚至多个指针同时维护链表不同位置的当前状态控制它们在正确的时机、以正确的步长移动。我经常把链表题比作“指针手术”。手术做得干净不干净看缝针顺序链表写得稳不稳看赋值顺序。一个疏忽链就断了程序就崩了。1.2 三道题的能力递进线单独刷一道题容易变成背模板把三道题放一起刷能清楚看到一条能力递进线。24 题教会你“修改链表之前必须知道自己现在站在哪”。它用单个 prev 指针站在待交换节点的前驱位置向后管理两个节点。如果把链表节点想象成一列火车车厢这道题就是“两节一对做接头重连”。19 题开始引入“相对位移”。快指针先走 N1 步然后快慢同步移动快指针到达尾部时慢指针刚好站在待删除节点的前驱。这里不再只看着眼前一个节点而是让两个指针相隔固定距离一起走天然需要你对“倒数第 N 个”这个描述有一个画面感。142 题则把“速度差”用到极致。快指针每次两步慢指针每次一步有环时必然追上。追上之后还要用数学关系找到环的入口。整个过程是判断型问题的经典套路先确认结果存在再精确定位。把这三题吃透链表题里的“单个指针操作”“双指针同速”“快慢指针变速”三类手法就全部过了一遍。后续再碰合并有序链表、旋转链表、排序链表你会发现上手速度快很多。2. 吃透虚拟头节点链表题的第一块基石2.1 为什么 dummy 节点能省掉一堆 if24 题和 19 题都可以用虚拟头节点dummy head来简化代码。它的作用用一句话就能说清让头节点不再是一个“特殊节点”。想象一下没有 dummy 的情况。你删除链表头节点时需要特殊处理 head 本身因为普通删除操作是“找到前驱然后改前驱的 next”。头节点压根没有前驱。如果不加判断直接把 head 删掉后续指针就会乱套。这时只能写if (head target) head head-next; else ...之类的分支代码立刻变丑还容易漏边界。一旦在链表头前面插入一个虚拟节点所有操作都统一成“站在 dummy 的位置处理 dummy-next”。你不再需要区分“处理的是不是头节点”因为 dummy 永远不参与业务逻辑它只是给你当踏板。删除、交换、逆序这类操作都能通过访问cur-next来定位真正要动的节点。提示dummy 节点存什么值无所谓通常写成 0。它的价值不在 val而在它提供的“前驱位置”让 include 头节点在内的所有节点都拥有统一的前驱边界从此消失。2.2 虚拟头节点使用的三个常见误区第一个误区最后顺手return head。这是最隐蔽的错误。一旦头节点被删或者被交换head 变量记录的还是旧地址它甚至可能已经指向被丢弃的节点。正确做法永远是return dummy-next让虚拟头节点重新导出当前链表的头部。第二个误区忘了 check 空链表。有的同学写了 dummy 就觉得万事大吉却忘了入参 head 可能本来就是 nullptr。虽然 24 题、19 题大多默认链表至少有一个节点但面试时最好还是显式处理一下把防御性思维展示出来。第三个误区把 dummy 也绕进赋值循环里。链表指针操作有条铁律先保存后修改。你要动cur-next先把它的原值用临时变量存下来再做赋值。临时变量不够就再声明一个链表题里多几个局部变量非常正常。宁可多写一行也不要让脏指针悄悄溜走。3. 24. 两两交换链表中的节点画图比写代码重要3.1 思路要点站在前驱节点做事假设链表是dummy - 1 - 2 - 3 - 4 - 5现在要交换 1 和 2。多数人的第一反应是直接盯住 1 和 2 两个节点动手。我更建议的方式是“向后管理”用一个 prev 指针站在待交换两个节点的前方一开始指向 dummy。这道题的关键动作是四个指针重连顺序不能乱。先声明两个局部变量 first 和 second把当前的两个节点固定下来first prev-next也就是节点 1。second first-next也就是节点 2。prev-next second让前驱先指向第二个节点。first-next second-next让第一个节点指向第三个节点完成“甩尾”。second-next first让第二个节点反过来指向第一个节点。prev first把游标向前推进两个位置。为什么一定要先保存 first 和 second因为执行第 3 步之后沿途的指针关系已经被改写如果不保存后面就再也取不到原来的“节点 1”和“节点 2”了。这两条赋值语句就像做手术时先把器官夹住固定再开始缝线。循环条件怎么写观察上面流程每轮开头我们都要求存在“两个相邻节点”可以交换所以条件是prev-next ! nullptr prev-next-next ! nullptr。也就是说剩余节点数 ≥ 2 时才进入循环剩余一个或空时直接结束正好处理了奇数长度链表的“最后一个节点不交换”。3.2 参考实现C 迭代版class Solution { public: ListNode* swapPairs(ListNode* head) { ListNode* dummy new ListNode(0); dummy-next head; ListNode* prev dummy; while (prev-next ! nullptr prev-next-next ! nullptr) { ListNode* first prev-next; ListNode* second first-next; prev-next second; first-next second-next; second-next first; prev first; } ListNode* ans dummy-next; delete dummy; return ans; } };注意 C 版我最后做了delete dummy。因为 dummy 是堆上 new 出来的节点返回前释放掉更严谨。很多教科书代码不释放LeetCode 评测也不会报内存泄漏但面试时主动讲一句“我会 delete 掉临时节点”属于亮点细节。当然如果你是为了快速刷题不 delete 也能跑只是长期习惯不好。注意循环条件判断必须“先当前节点后下一个节点”。写成prev-next-next prev-next会导致空链表访问空指针的 next直接崩溃。顺序问题在链表题里不是小事。3.3 递归解法与边界处理迭代法写起来长但好理解。这里顺带提一下递归版本面试偶尔会问“能不能用递归写”class Solution { public: ListNode* swapPairs(ListNode* head) { if (head nullptr || head-next nullptr) return head; ListNode* newHead head-next; head-next swapPairs(newHead-next); newHead-next head; return newHead; } };递归版的核心逻辑是先处理子问题swapPairs(newHead-next)把后面一堆节点两两交换好让 head 去收尾。递归版的出口条件是head nullptr || head-next nullptr正好对应链表为空或只剩一个节点的边界。两种解法选哪种我建议面试时先说迭代版因为不用解释递归栈也不容易超时。递归版适合已经熟练掌握题意的同学或者作为“优化思路”补充展示。4. 19. 删除链表的倒数第N个节点双指针定长滑块4.1 思路推导快指针为什么走 N1 步最容易想到的解法是两遍扫描先遍历一次求链表长度 L再从头走 L-N 步找到待删节点。也能 AC但面试官多半会追问“能不能只遍历一次”这时候双指针法就该登场了。双指针做法的核心是“让两个指针之间保持固定间隔”。fast 先走 N1 步slow 留在原地都把 dummy 作为起点。这时 fast 在 slow 前方第 N1 个位置。接着两个指针同步每次走一步当 fast 走到链表尾部的 nullptr 时slow 恰好站在待删除节点的前驱。这里容易犯迷糊的是“快指针到底先走 N 步还是 N1 步”。如果你只想让 slow 最后停在“待删除节点本身”那先走 N 步就够了。但删除一个节点需要改它的前驱所以你得额外维护一个前驱变量代码变啰嗦。走 N1 步是“让 slow 直接到达前驱”的聪明解法多走这一步省掉一堆额外判断还顺便统一了边界。同理如果需要“查找倒数第 K 个节点”快指针先走 K 步就够了因为查询只是读取不需要改前驱。删除和查找对位置的要求不同步数自然不同这个细节值得记住。4.2 参考实现Pythonclass Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) - Optional[ListNode]: dummy ListNode(0, head) fast dummy slow dummy # fast 先走 n1 步为了让 slow 最后停在待删节点的前驱 for _ in range(n 1): fast fast.next # 两个指针同步走 while fast: fast fast.next slow slow.next # 删除目标节点 slow.next slow.next.next return dummy.nextPython 的 LeetCode 环境自带Optional[ListNode]直接用即可。ListNode(0, head)这种写法依赖 ListNode 的构造函数支持两个参数如果本地环境不支持写成dummy ListNode(0); dummy.next head最稳妥。这段代码里最容易被忽视的是循环while fast:——它每轮只走一步。有人会手快写成while fast.next:结果 fast 走不到末尾的 nullptr慢指针位置也跟着错。老实说这题能一次写对的人靠的不是聪明而是对“步数”这两个字的敏感。4.3 面试追问为什么返回 dummy.next 而不是 head很多题解都写了“返回 dummy.next”但能说清楚为什么的人不多。假如删除的恰好是原头节点例如链表1 - 2 - 3N3删除倒数第 3 个也就是节点 1。如果最后return headhead 还是指向节点 1 的旧地址但这个节点已经从新链表中断开了返回旧头导致结果错误。dummy-next 则永远指向“当前链表真正意义上的头节点”。删除后它自动更新为新头无论被删的是哪个位置都正确。面试官如果追问到这里你也正好有机会展示对“虚拟头节点设计动机”的理解我记得一句话就能答完dummy 把改动的副作用统一收口到 dummy-next头节点不再是特殊节点。另外这套“定长滑块”的思路稍加变化就可以解很多题比如求链表中间节点快指针走两步慢走一步、划分链表前后双指针等等。19 题不只是背代码它是双指针思维的一次总演练。5. 142. 环形链表 IIFloyd 判圈算法的全推导5.1 如何判断有环快慢指针的速度差先解决“有没有环”的问题。思路很简单慢指针 slow 每次走 1 步快指针 fast 每次走 2 步同时从 head 出发。如果链表中存在环fast 一定会“套圈”追上 slow如果链表无环fast 会率先走到 nullptr。原理也不难理解。把环想象成一条圆形跑道slow 和 fast 都在里面跑。slow 相对 fast 的速度差是每个时间步多跑 1 步距离差逐步缩小一定会在某个时刻相遇。这个相遇点一定在环内这是后面找入口的前提。关键细节在于代码顺序。两个指针初始化都为 head循环里必须“先移动、后判断相等”。如果反过来先判断初始状态两个指针相等你会误以为“存在环”实际只是起点相同。这点我见过太快的人摔过跤。5.2 找环入口相遇之后的数学推导题目要求返回环的入口节点而不是相遇点。这里需要推导一下。记链表头 head 到环入口的距离为a环入口到相遇点的距离为b相遇点继续前进回到环入口的距离为c。那么环的总长度为b c。慢指针从头到相遇点一共走了a b。快指针呢它走了a b k * (b c)其中 k 是快指针在环内绕的圈数至少是 1。因为快指针速度是慢指针的 2 倍所以得到等式a b k * (b c) 2 * (a b)化简得到k * (b c) a b也就是a k * (b c) - b (k - 1) * (b c) c当 k 1 时就有a c。翻译成人话就是从 head 走到环入口和从相遇点再走回环入口距离一样。就算 k 1等式右侧也只是多了几个完整的环长也就是说“从相遇点走 a 步”绕了几圈之后照样落在环入口。于是解法水落石出把 fast 重置到 head两个指针改成同步一步共同前进再次相遇的位置就是环的入口。这个推导一定要自己手算一遍不要只背结论。面试官问“为什么相遇之后同步走就能找到入口”时能流利讲出“a c”的由来比干巴巴说“因为规律如此”要强太多。5.3 参考实现Pythonclass Solution: def detectCycle(self, head: Optional[ListNode]) - Optional[ListNode]: slow head fast head # 第一阶段判断是否有环 while fast and fast.next: slow slow.next fast fast.next.next if slow fast: break else: return None # 无环 # 第二阶段找入口 fast head while slow ! fast: slow slow.next fast fast.next return slow这里用while ... else写得很 Pythonic快指针跑到空说明无环走 else 分支返回 None。如果是因为相遇而 break则进入第二阶段。第二阶段把 fast 拉回 head两个指针各走一步第一次相等的位置就是入口。注意第二阶段无需再判断节点是否为空因为前面已经确定存在环两个指针迟早相遇。5.4 容易忽略的边界条件边界一空链表或者只有一个节点的链表。循环条件fast and fast.next会直接不成立走到 else 返回 None逻辑安全。边界二整个链表就是一个大环。此时 a 0head 自己就是入口。第二阶段中 fast 回到 head 后slow 仍在相遇点两者同步走第一次相遇点就是 head代码天然正确。边界三快指针会不会“跳过”慢指针导致无法相遇不会。因为两者相对速度是“每轮多走 1 步”距离差严格递减不可能跨越式错过。这一点是 Floyd 算法的根基如果有人问你为什么快指针走两步、不走三步答案也在这里速度差为 1保证不跳过。6. 三题联刷后的高频错误与避坑清单6.1 易错点速查表三题连着刷完我把最容易出错的点整理成一张速查表刷完题后对着自查一遍比盲目刷新题有效得多。错误类型问题描述正确做法返回值用错24、19 题最后return head统一return dummy-next让虚拟头导出最新链表头断链修改prev-next时没保存后续节点先声明 first、second 固定节点再开始赋值循环条件判断顺序错写prev-next-next prev-next先判断当前节点存在再判断下一个节点双指针初始化比较时机错142 题一进循环就判断相等先移动指针后比较避免初始相等造成误判删除倒数第 N 步数错快指针只走 N 步删除场景需要走 N1 步让慢指针停在目标前驱忘记更新 prev24 题每轮交换完没prev first每轮结束推进游标否则下一轮还会处理旧节点while 死循环142 题有环时不知道何时停利用 fast 为空判断无环同时防止fast.next为空这张表是给我自己复盘用的你刷完也可以照着过一遍。我发现大多数 Bug 都出在最不以为然的细节上尤其是指针的“保存与归还”。6.2 面试现场的两个实用技巧记录两个在面试中非常加分的习惯。第一个是“先画图再写代码”。链表题几乎全部依赖空间想象拿起笔在草稿纸上画四个方格子代表节点标好 prev、first、second顺着代码逐行走一遍很多看似复杂的逻辑会变得无比清晰。面试官看到你有画图动作第一反应是“这个人会写代码”而不是背模板。第二个是“主动说出循环不变量”。比如 24 题的 while 循环中prev 始终是当前待交换两节点的前驱19 题的循环始终维持 fast 和 slow 之间相差 N 个节点142 题的循环不变量则是快慢指针的相对速度恒定为 1。能在代码写完后把这个话说出口面试官对算法功底的评估会上一个台阶。6.3 后续扩展练习方向三题刷完推荐几个“同思路”的后续题K 个一组翻转链表24 题的强化版把“两两交换”升级为“K 个一组逆序”。旋转链表结合链表长度取余再加上双指针找断点。链表的中间结点快慢指针的基础应用142 题的前置热身。环形链表只判断有环无环不找入口适合作为 142 的第一遍验证。删除倒数第 K 个节点 / 查找倒数第 K 个节点19 题的一题两问变体用来检测你是否有“步数感”。我个人刷链表专题的经验是第一遍刷不求快求“每一步指针变化都对得上画图”第二遍刷要尝试不给草稿写完一整段代码第三遍再挑战“一次通过”。24 题我第一次刷的时候花了一整晚才彻底想明白后来刷到 142 题做完数学推导才真正感觉到链表的恐惧感消失。最后说个亲身感悟算法面试里的链表题考的不是天赋而是熟练度。把画图、循环不变量、dummy 节点这三个习惯刻进肌肉记忆你写任何链表题都会快不少。这三道题适合在刷题计划里的第二到第三周反复刷三遍每遍都蒙住答案自己重写。基本功这种事情偷不得懒也没有捷径可走。