链表和算法这两个词放在一起很多人的第一反应是“面试要考”“LeetCode刷题”第二反应可能就是“指针绕来绕去边界条件一堆”。我在带新人和做技术评审的时候发现链表类题目是很多人从“看得懂题解”到“能独立写对”之间的一道坎——不是因为它难而是因为它考察的东西太底层你有没有真正理解引用的本质能不能在脑子里把节点的指向关系画清楚写代码的时候会不会处理空指针和边界。这篇博文我就挑三道最经典、也是出镜率最高的链表算法题来做一次完整拆解单链表反转、链表环检测、删除链表倒数第N个节点。三道题背后其实覆盖了链表题的大部分核心技巧三指针迭代、递归思路、快慢指针、dummy节点法。如果你正在准备算法面试或者刚学完数据结构想找点实操练手又或者写业务代码多年但对链表操作总有点发怵那这篇文章应该能帮你在一个下午之内把链表题的地基打扎实。我不打算把题解往你面前一摆就完事而是会把每个关键步骤的“为什么”讲清楚为什么这样改指针不会断链为什么快慢指针一定会相遇为什么dummy节点能省掉那么多if判断知道了这些你以后遇到再花哨的链表变种题也知道怎么下手。1. 三道题的整体设计思路与解题框架很多人刷链表题最大的误区是上来就背代码。背下来的东西碰到原题还能默写但只要面试官稍微换一下条件比如“反转前N个节点”“只检测环但不要找入口”“删除倒数第N个节点的同时还要返回头节点”马上就卡壳。所以我更建议你先建立一套“链表通用解题框架”再落到具体题目上。链表操作本质上就两件事改指向和防断链。改指向好理解比如要把A节点指向C就把A的next从B改成C。防断链就一句话在你改动任何一个节点的next之前先确保这个节点的后继节点已经被引用保存了不然你一指过去后面的链表就找不回来了。基于这两件事链表题有四个高频惯用法这三道题全部会用到prev / curr / next 三指针法链表反转、删除节点的标准套路。核心是维护“前一个节点”“当前节点”“下一个节点”三个指针保证任意时刻都知道前后关系不会断链。快慢双指针找中间节点、检测环、找倒数第K个节点的万能工具。核心思想是两个指针步长不同让它们之间产生“距离差”利用这个距离差来定位。dummy节点哑元节点当操作可能涉及头节点时在头部之前垫一个哨兵节点让头节点的处理和普通节点完全一致省去大量“如果删的是头节点怎么办”的分支判断。递归的“递”与“归”反转链表这类问题天然有递归结构理解“先走到链表末尾再一层层改指向”的回归过程是进阶必备。你可以把这篇文章里的三道题当成三个“套路模板”每个模板都带一套完整的思考流程先想怎么暴力做再想怎么优化最后落地到代码边写边检查边界。2. 第一道单链表反转——三指针法与递归写法单链表反转是链表题里最基础、最常考的一道也是很多学校“单链表的基本操作实验”里的保留项目。题目描述很简单给你一个单链表的头节点 head把它整个反转过来返回反转后的新头节点。2.1 迭代法三个指针怎么配合迭代反转的核心思路就是在遍历链表的过程中把每个节点的 next 指向前一个节点。问题来了当你把当前节点的 next 指向它前一个节点之后它原本的后一个节点就丢了因为你已经改了 next。所以必须在改之前先用一个临时指针把后继节点保存下来。代码长这样Cstruct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} }; ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; // 前一个节点初始为空 ListNode* curr head; // 当前节点 while (curr ! nullptr) { ListNode* next curr-next; // 先保存后继 curr-next prev; // 反转指向 prev curr; // 向后移动 curr next; } return prev; // 循环结束时 prev 就是新头 }三个指针的分工需要掰开揉碎讲清楚prev是“已经反转好的那段链表的头”初始时是 nullptr因为第一个节点的 next 最终要指向空。curr是“当前正在处理的节点”每一步都会把它的 next 翻到 prev 上。next是“当前节点的原始后继”它唯一的任务就是防止 curr 反转后我们丢了对链表后半部分的访问。每一步循环结束前三个指针集体后移一格prev 变成 currcurr 变成 next。循环条件curr ! nullptr保证了链表为空时直接返回 nullptr单节点链表时循环只走一次prev 变成那个单节点返回正确。有的同学喜欢先画图再写代码这是很好的习惯。你不需要画得精细画出三个节点、两三条箭头把每一次循环之后箭头怎么变、指针怎么移画清楚这道题就永远不会写错。2.2 递归解法搞清楚“递”和“归”递归写法代码更短但理解门槛更高ListNode* reverseList(ListNode* head) { if (head nullptr || head-next nullptr) { return head; } ListNode* newHead reverseList(head-next); head-next-next head; // 让下一个节点反过来指向当前节点 head-next nullptr; // 断开当前节点和下一个节点的正向连接 return newHead; }第一次看这段代码的人十有八九会卡在head-next-next head这一句上。我来顺着递归的实际执行过程走一遍。假设链表是 1 - 2 - 3 - nullptr。调用reverseList(1)时它先去调用reverseList(2)reverseList(2)又去调用reverseList(3)。到reverseList(3)时因为 3 的 next 是 nullptr直接返回 3。这时候递归开始“归”。回到reverseList(2)这一层此时 head 是 2head-next 是 3。执行head-next-next head就是把 3 的 next 指向 2链表变成了 1 - 2 - 3。然后head-next nullptr把 2 到 3 的正向连接断掉变为 1 - 2 - 3。返回 newHead也就是 3。再回到reverseList(1)这一层head 是 1head-next 是 2。执行head-next-next head把 2 的 next 指向 1链表变成 1 - 2 - 3。然后head-next nullptr断掉 1 到 2 的连接最终变成 1 - 2 - 3。返回 newHead也就是原来的尾节点 3。递归的核心是你不需要关心下层递归做了什么只需要相信它一定正确地把后半段链表反转了并且把新的头返回给你。你要做的只是处理当前节点和它下一个节点之间的关系。这种“相信递归”的思维方式在链表递归题目里非常重要。2.3 变体反转前N个节点面试官很喜欢在原题基础上加需求最常见的变体是“反转链表的前N个节点”。我不能完整展开所有代码但可以给你一个关键的思考方向迭代法里你需要先找到第N个节点把它和第N1个节点的连接记住反转前N个最后把头部的 next 接到第N1个节点上。这里最容易被坑的就是“第N个节点之后的尾巴别忘了接回去”一旦漏掉整个链表后半部分就丢了。3. 第二道链表环检测——快慢指针与环入口第二道经典题是“判断链表中是否有环”进阶版是“找到环的入口节点”。这两问放在一起来讲因为它们的核心是同一个机制快慢双指针。3.1 快慢指针为什么有效先看基础版题给定一个链表头 head判断链表中是否有环。最直观的做法是用哈希表记录访问过的节点每遍历一个节点就查一下之前有没有出现过。这个做法时间复杂度 O(n)空间复杂度 O(n)能不能把空间优化到 O(1)可以用快慢指针。快慢指针的思路定义慢指针 slow 每次走一步快指针 fast 每次走两步从 head 同时出发。如果链表中没有环fast 会先走到 nullptr循环结束返回 false。如果链表中有环slow 和 fast 最终会在环内相遇。很多人不理解“为什么快指针每次走两步而不是走三步四步”我解释一下假设链表进入环之前的长度为 a环的长度为 b。当慢指针到达环入口时快指针已经在环内走了若干步。两个指针都在环内运动快指针每次比慢指针多走一步所以相当于快指针在以“每单位时间减少1”的速度追赶慢指针。只要环的长度是有限的这个距离差一定能被缩小到0。如果快指针每次走三步那么它和慢指针之间的距离差每次减少2可能恰好从“差1”跳到“差-1”也就是直接错过去了反而不好分析。走两步最简单也最安全数学上一定相遇。这个思路也可以理解成两个人绕操场跑圈一个快一个慢只要跑道是闭合的跑得快的人终究会套圈追上跑得慢的人。3.2 判断是否有环的代码实现bool hasCycle(ListNode *head) { if (head nullptr || head-next nullptr) { return false; } ListNode *slow head; ListNode *fast head-next; // 这里也可以同时从 head 出发先走一步区分即可 while (slow ! fast) { if (fast nullptr || fast-next nullptr) { return false; } slow slow-next; fast fast-next-next; } return true; }需要注意的细节有两点。第一快指针移动前必须判断fast和fast-next都不为空否则空指针访问直接崩溃。这也是链表题里最容易犯的错——不能等到下一次循环再去判断因为快指针一次要跳两步跳之前必须确认第一步和第二步都能落下去。第二初始化时可以让 slow 从 head、fast 从 head-next 出发这样循环条件slow ! fast在无环情况下更容易退出也可以两者都从 head 出发但那样需要先跑一次再进入判断。两种写法都对只要你能自洽地解释清楚面试官通常不会纠结。如果你用 Python逻辑完全一致class ListNode: def __init__(self, x): self.val x self.next None def hasCycle(head: ListNode) - bool: if not head or not head.next: return False slow, fast head, head.next while slow ! fast: if not fast or not fast.next: return False slow slow.next fast fast.next.next return True3.3 进阶怎么找环的入口节点基础版做完了面试官大概率会追问一句“你能找到环的入口吗”这里有一个非常经典的结论当快慢指针第一次在环内相遇后把一个指针移回 head然后把两个指针的步长都改为1各自再走一单步它们相遇的位置就是环的入口。这个结论的数学证明非常重要它就是“经验注入”里的关键点。我带你推导一次。从头节点出发到环入口的距离记为 a环入口到第一次相遇点的距离记为 b从第一次相遇点继续走回到环入口的距离记为 c。那么环的周长是 b c。当 slow 和 fast 第一次相遇时slow 走了 a b 步fast 走了 a b k*(b c) 步k是快指针在环内多绕的圈数至少为1。因为 fast 的速度是 slow 的两倍所以2 * (a b) a b k * (b c)化简得到a b k * (b c)也就是 a k * (b c) - b。当 k 1 时a c。意思是从起点到环入口的距离恰好等于从第一次相遇点继续走到环入口的距离。所以让一个指针从起点走另一个从相遇点走步长为1它们会恰好在环入口相遇。k 1 时等式同样成立只是第二个指针需要多绕几圈而已经但最终相遇点仍然是环入口。有了这个数学结论代码就很简单先用快慢指针找到相遇节点然后把任意一个指针重置为 head两者同步走相遇即入口。ListNode *detectCycle(ListNode *head) { ListNode *slow head, *fast head; while (true) { if (fast nullptr || fast-next nullptr) { return nullptr; } slow slow-next; fast fast-next-next; if (slow fast) { break; } } fast head; while (slow ! fast) { slow slow-next; fast fast-next; } return slow; }面试时如果能把这个推导过程写出来或讲清楚基本就能让面试官确认你确实理解了算法原理而不是背了题解。4. 第三道删除链表倒数第N个节点——dummy节点与双指针第三道选取的是“删除链表的倒数第N个节点”。在 leetcode 上对应的题号是 19属于中等难度的高频题。它考察的核心是一次遍历情况下怎么只用一个指针协调好前后距离以及头节点可能被删除时怎么让代码统一处理。4.1 为什么要用双指针而不是两次遍历最简单直接的方法是先遍历一遍链表得到链表总长度 L那么倒数第N个节点就是正数第 L-N1 个节点再走第二遍把它删掉。这当然能过但面试官想看到的优化是能不能只遍历一遍可以而且方法很优雅。设置两个指针first 和 second初始都指向 dummy 头节点。先让 first 指针向前走 N1 步然后 first 和 second 以相同速度一起走。当 first 走到链表的末尾nullptr时second 恰好位于要删除节点的前一个节点。这时执行second-next second-next-next就完成了删除。这里有一个细节为什么 first 要先走 N1 步而不是 N 步因为我们需要 second 停在“待删除节点的前一个节点”上。如果 first 先走 N 步那么当 first 到末尾时second 正好停在待删除节点上你还需要额外的 prev 指针才能完成删除。先走 N1 步能让 second 天然指向待删除节点的前一个节点代码更简洁。4.2 dummy 节点省掉了最恶心的边界判断如果链表是 [1,2] 让你删倒数第2个节点删完应该得到 [2]。头节点1被删了那返回值就不能再是原来的 head 了得返回 head-next。不处理的话很多人会在这类边界 case 上翻车。解决办法就是在真正的头节点之前加一个哨兵节点 dummy把整个链表变成 dummy - head - ...。这样即使要删的是原头节点dummy 的下一个节点还是能正常更新最后你只需要返回 dummy-next 就行完全不需要关心头节点有没有被删。ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy new ListNode(0); dummy-next head; ListNode* first dummy; ListNode* second dummy; // first 先走 n1 步 for (int i 0; i n; i) { first first-next; } // 同步前进 while (first ! nullptr) { first first-next; second second-next; } // 删除倒数第 n 个节点 ListNode* target second-next; second-next second-next-next; delete target; // C 记得释放内存 return dummy-next; }这里还有两个容易忽略的小问题。第一个是for循环里走 N1 步时如果链表长度刚好等于 N比如链表长度是2N也是2删除倒数第2个节点那么 first 先走3步会走到 nullptr 吗不会因为 first 从 dummy 出发走 3 步刚好到 nullptr 前面的最后一个节点再往后才是 nullptr。你仔细数一下dummy - node1 - node2 - nullptr从 dummy 起步走一步到 node1走两步到 node2走三步到 nullptr。所以这里 for 循环次数是i n当 n2 时循环3次first 正好停在 nullptr然后 while 循环直接跳过second 保持在 dummy删除 dummy-next也就是原链表第一个节点逻辑完全正确。第二个是内存释放。C 的链表操作需要手动管理内存删除节点后要用delete释放掉否则会有内存泄漏。虽然刷题平台一般不检查这个但你写生产代码或者和面试官讨论的时候能主动说出“记得 delete”会很加分。Python 版本需要注意的点不同Python 没有指针但有引用同样可以用双指针和 dummy 节点。不同之处在于你不需要手动释放内存不需要 delete所以代码更清爽def removeNthFromEnd(head: ListNode, n: int) - ListNode: dummy ListNode(0) dummy.next head first dummy second dummy for _ in range(n 1): first first.next while first: first first.next second second.next second.next second.next.next return dummy.next4.3 延伸快慢指针在查找场景里的通用性删除倒数第N个节点这个“双指针先走N步再同步移动”的手法其实是一个通用公式可以延展到很多场景。比如“找链表中间节点”一个 fast 指针每次走两步一个 slow 指针每次走一步当 fast 走到末尾时slow 正好在中间。再比如“判断链表是否成环”本质上也是同一套指针体系。所以你看这三道题虽然各自独立但内里的核心套路是高度统一的先是 dummy 节点解决边界再是双指针制造距离差最后是空指针检查兜底。我把这三个要素背熟之后遇到别的链表题心里就有底了。5. 实操中的常见坑与调试技巧链表题的坑非常固定踩过一次以后记住了下次就不会再犯。我把这些年见到的、自己踩过的高频坑汇总成一个速查表方便你复习常见问题出现原因解决方案与检查思路空指针异常访问了 nullptr 的 next 或 val任何node-next使用前先保证 node 不为空涉及快指针时还要保证fast-next不为空链表断连后半部分丢失修改 next 之前没有保存后继节点养成习惯改指针之前先想“原来的下一个节点还在不在我的手里”头节点丢失删除头节点或反转后没更新头引用使用 dummy 节点或记住永远更新 head 变量的时机形成环程序死循环反转或删除时把某个节点的 next 指回了自己或前驱反转链表最后一定要把原头节点的 next 置为 nullptr调试时加一个步数上限返回了错误的“头”反转后返回了原来的 head反转链表循环结束后的 prev 才是新头删除头节点时用 dummy-next除了这些调试链表题有一个非常好用的方法画图。很多人一看到指针就头晕是因为只在脑子里凭空想象。我的建议是找一支笔一张纸或者用白板把所有节点画成方框next 画成箭头然后每执行一行代码就在图上走一遍。我面试候选人的时候如果一个人能在白板上把链表的图画清楚代码基本不会有大问题。另一个实操技巧是打印遍历。你可以稍微写一个辅助函数把链表的节点值依次打印出来在关键操作前后各打印一次立刻就知道有没有断链、有没有成环。对于环检测题打印时要加一个步数限制比如最多打印20步防止死循环把终端刷爆。6. 调试与追溯三道题一网打尽后的下一步写到这里三道题讲完了单链表反转教你三指针法和递归思维环检测与环入口带你从快慢指针到数学推导删除倒数第N个节点则展示了 dummy 节点和双指针配合的威力。它们合起来几乎覆盖了链表面试里八成以上的考点。我个人在实际带人的过程中体会最深的一点是链表题千万别背一定要动手画、动手写。你可以看完题解以后合上屏幕从零开始自己写一遍。第一遍可能憋很久、或者写出各种 bug这太正常了。等你能在三五分钟内把这三道题默写出来并且能把为什么不这么写就会错的原因讲明白你的链表基本功就真的过关了。最后再分享一个小技巧这三个算法背后的“双指针”“三指针”“哑元节点”不是链表独有数组、字符串、树的很多问题也用得上。你可以尝试用一个通用的“双指针框架”去重新看一遍你刷过的题会发现很多题解的开头都会长得很像。理解了这一层你就不只是在刷三道题而是建立了一套属于自己的算法解题框架。这篇文章的代码片段C 和 Python 版本我都给了你可以都用自己熟悉的语言跑一遍。跑通了以后推荐去刷同类型的题目验证一下环形链表 II、反转链表 II、两两交换链表中的节点、删除排序链表中的重复元素。这几道题看起来各不相同但底层套路就是我们今天讲的这一套。练完它们你对链表操作的肌肉记忆就真正形成了。
链表和算法这两个词放在一起很多人的第一反应是“面试要考”“LeetCode刷题”第二反应可能就是“指针绕来绕去边界条件一堆”。我在带新人和做技术评审的时候发现链表类题目是很多人从“看得懂题解”到“能独立写对”之间的一道坎——不是因为它难而是因为它考察的东西太底层你有没有真正理解引用的本质能不能在脑子里把节点的指向关系画清楚写代码的时候会不会处理空指针和边界。这篇博文我就挑三道最经典、也是出镜率最高的链表算法题来做一次完整拆解单链表反转、链表环检测、删除链表倒数第N个节点。三道题背后其实覆盖了链表题的大部分核心技巧三指针迭代、递归思路、快慢指针、dummy节点法。如果你正在准备算法面试或者刚学完数据结构想找点实操练手又或者写业务代码多年但对链表操作总有点发怵那这篇文章应该能帮你在一个下午之内把链表题的地基打扎实。我不打算把题解往你面前一摆就完事而是会把每个关键步骤的“为什么”讲清楚为什么这样改指针不会断链为什么快慢指针一定会相遇为什么dummy节点能省掉那么多if判断知道了这些你以后遇到再花哨的链表变种题也知道怎么下手。1. 三道题的整体设计思路与解题框架很多人刷链表题最大的误区是上来就背代码。背下来的东西碰到原题还能默写但只要面试官稍微换一下条件比如“反转前N个节点”“只检测环但不要找入口”“删除倒数第N个节点的同时还要返回头节点”马上就卡壳。所以我更建议你先建立一套“链表通用解题框架”再落到具体题目上。链表操作本质上就两件事改指向和防断链。改指向好理解比如要把A节点指向C就把A的next从B改成C。防断链就一句话在你改动任何一个节点的next之前先确保这个节点的后继节点已经被引用保存了不然你一指过去后面的链表就找不回来了。基于这两件事链表题有四个高频惯用法这三道题全部会用到prev / curr / next 三指针法链表反转、删除节点的标准套路。核心是维护“前一个节点”“当前节点”“下一个节点”三个指针保证任意时刻都知道前后关系不会断链。快慢双指针找中间节点、检测环、找倒数第K个节点的万能工具。核心思想是两个指针步长不同让它们之间产生“距离差”利用这个距离差来定位。dummy节点哑元节点当操作可能涉及头节点时在头部之前垫一个哨兵节点让头节点的处理和普通节点完全一致省去大量“如果删的是头节点怎么办”的分支判断。递归的“递”与“归”反转链表这类问题天然有递归结构理解“先走到链表末尾再一层层改指向”的回归过程是进阶必备。你可以把这篇文章里的三道题当成三个“套路模板”每个模板都带一套完整的思考流程先想怎么暴力做再想怎么优化最后落地到代码边写边检查边界。2. 第一道单链表反转——三指针法与递归写法单链表反转是链表题里最基础、最常考的一道也是很多学校“单链表的基本操作实验”里的保留项目。题目描述很简单给你一个单链表的头节点 head把它整个反转过来返回反转后的新头节点。2.1 迭代法三个指针怎么配合迭代反转的核心思路就是在遍历链表的过程中把每个节点的 next 指向前一个节点。问题来了当你把当前节点的 next 指向它前一个节点之后它原本的后一个节点就丢了因为你已经改了 next。所以必须在改之前先用一个临时指针把后继节点保存下来。代码长这样Cstruct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} }; ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; // 前一个节点初始为空 ListNode* curr head; // 当前节点 while (curr ! nullptr) { ListNode* next curr-next; // 先保存后继 curr-next prev; // 反转指向 prev curr; // 向后移动 curr next; } return prev; // 循环结束时 prev 就是新头 }三个指针的分工需要掰开揉碎讲清楚prev是“已经反转好的那段链表的头”初始时是 nullptr因为第一个节点的 next 最终要指向空。curr是“当前正在处理的节点”每一步都会把它的 next 翻到 prev 上。next是“当前节点的原始后继”它唯一的任务就是防止 curr 反转后我们丢了对链表后半部分的访问。每一步循环结束前三个指针集体后移一格prev 变成 currcurr 变成 next。循环条件curr ! nullptr保证了链表为空时直接返回 nullptr单节点链表时循环只走一次prev 变成那个单节点返回正确。有的同学喜欢先画图再写代码这是很好的习惯。你不需要画得精细画出三个节点、两三条箭头把每一次循环之后箭头怎么变、指针怎么移画清楚这道题就永远不会写错。2.2 递归解法搞清楚“递”和“归”递归写法代码更短但理解门槛更高ListNode* reverseList(ListNode* head) { if (head nullptr || head-next nullptr) { return head; } ListNode* newHead reverseList(head-next); head-next-next head; // 让下一个节点反过来指向当前节点 head-next nullptr; // 断开当前节点和下一个节点的正向连接 return newHead; }第一次看这段代码的人十有八九会卡在head-next-next head这一句上。我来顺着递归的实际执行过程走一遍。假设链表是 1 - 2 - 3 - nullptr。调用reverseList(1)时它先去调用reverseList(2)reverseList(2)又去调用reverseList(3)。到reverseList(3)时因为 3 的 next 是 nullptr直接返回 3。这时候递归开始“归”。回到reverseList(2)这一层此时 head 是 2head-next 是 3。执行head-next-next head就是把 3 的 next 指向 2链表变成了 1 - 2 - 3。然后head-next nullptr把 2 到 3 的正向连接断掉变为 1 - 2 - 3。返回 newHead也就是 3。再回到reverseList(1)这一层head 是 1head-next 是 2。执行head-next-next head把 2 的 next 指向 1链表变成 1 - 2 - 3。然后head-next nullptr断掉 1 到 2 的连接最终变成 1 - 2 - 3。返回 newHead也就是原来的尾节点 3。递归的核心是你不需要关心下层递归做了什么只需要相信它一定正确地把后半段链表反转了并且把新的头返回给你。你要做的只是处理当前节点和它下一个节点之间的关系。这种“相信递归”的思维方式在链表递归题目里非常重要。2.3 变体反转前N个节点面试官很喜欢在原题基础上加需求最常见的变体是“反转链表的前N个节点”。我不能完整展开所有代码但可以给你一个关键的思考方向迭代法里你需要先找到第N个节点把它和第N1个节点的连接记住反转前N个最后把头部的 next 接到第N1个节点上。这里最容易被坑的就是“第N个节点之后的尾巴别忘了接回去”一旦漏掉整个链表后半部分就丢了。3. 第二道链表环检测——快慢指针与环入口第二道经典题是“判断链表中是否有环”进阶版是“找到环的入口节点”。这两问放在一起来讲因为它们的核心是同一个机制快慢双指针。3.1 快慢指针为什么有效先看基础版题给定一个链表头 head判断链表中是否有环。最直观的做法是用哈希表记录访问过的节点每遍历一个节点就查一下之前有没有出现过。这个做法时间复杂度 O(n)空间复杂度 O(n)能不能把空间优化到 O(1)可以用快慢指针。快慢指针的思路定义慢指针 slow 每次走一步快指针 fast 每次走两步从 head 同时出发。如果链表中没有环fast 会先走到 nullptr循环结束返回 false。如果链表中有环slow 和 fast 最终会在环内相遇。很多人不理解“为什么快指针每次走两步而不是走三步四步”我解释一下假设链表进入环之前的长度为 a环的长度为 b。当慢指针到达环入口时快指针已经在环内走了若干步。两个指针都在环内运动快指针每次比慢指针多走一步所以相当于快指针在以“每单位时间减少1”的速度追赶慢指针。只要环的长度是有限的这个距离差一定能被缩小到0。如果快指针每次走三步那么它和慢指针之间的距离差每次减少2可能恰好从“差1”跳到“差-1”也就是直接错过去了反而不好分析。走两步最简单也最安全数学上一定相遇。这个思路也可以理解成两个人绕操场跑圈一个快一个慢只要跑道是闭合的跑得快的人终究会套圈追上跑得慢的人。3.2 判断是否有环的代码实现bool hasCycle(ListNode *head) { if (head nullptr || head-next nullptr) { return false; } ListNode *slow head; ListNode *fast head-next; // 这里也可以同时从 head 出发先走一步区分即可 while (slow ! fast) { if (fast nullptr || fast-next nullptr) { return false; } slow slow-next; fast fast-next-next; } return true; }需要注意的细节有两点。第一快指针移动前必须判断fast和fast-next都不为空否则空指针访问直接崩溃。这也是链表题里最容易犯的错——不能等到下一次循环再去判断因为快指针一次要跳两步跳之前必须确认第一步和第二步都能落下去。第二初始化时可以让 slow 从 head、fast 从 head-next 出发这样循环条件slow ! fast在无环情况下更容易退出也可以两者都从 head 出发但那样需要先跑一次再进入判断。两种写法都对只要你能自洽地解释清楚面试官通常不会纠结。如果你用 Python逻辑完全一致class ListNode: def __init__(self, x): self.val x self.next None def hasCycle(head: ListNode) - bool: if not head or not head.next: return False slow, fast head, head.next while slow ! fast: if not fast or not fast.next: return False slow slow.next fast fast.next.next return True3.3 进阶怎么找环的入口节点基础版做完了面试官大概率会追问一句“你能找到环的入口吗”这里有一个非常经典的结论当快慢指针第一次在环内相遇后把一个指针移回 head然后把两个指针的步长都改为1各自再走一单步它们相遇的位置就是环的入口。这个结论的数学证明非常重要它就是“经验注入”里的关键点。我带你推导一次。从头节点出发到环入口的距离记为 a环入口到第一次相遇点的距离记为 b从第一次相遇点继续走回到环入口的距离记为 c。那么环的周长是 b c。当 slow 和 fast 第一次相遇时slow 走了 a b 步fast 走了 a b k*(b c) 步k是快指针在环内多绕的圈数至少为1。因为 fast 的速度是 slow 的两倍所以2 * (a b) a b k * (b c)化简得到a b k * (b c)也就是 a k * (b c) - b。当 k 1 时a c。意思是从起点到环入口的距离恰好等于从第一次相遇点继续走到环入口的距离。所以让一个指针从起点走另一个从相遇点走步长为1它们会恰好在环入口相遇。k 1 时等式同样成立只是第二个指针需要多绕几圈而已经但最终相遇点仍然是环入口。有了这个数学结论代码就很简单先用快慢指针找到相遇节点然后把任意一个指针重置为 head两者同步走相遇即入口。ListNode *detectCycle(ListNode *head) { ListNode *slow head, *fast head; while (true) { if (fast nullptr || fast-next nullptr) { return nullptr; } slow slow-next; fast fast-next-next; if (slow fast) { break; } } fast head; while (slow ! fast) { slow slow-next; fast fast-next; } return slow; }面试时如果能把这个推导过程写出来或讲清楚基本就能让面试官确认你确实理解了算法原理而不是背了题解。4. 第三道删除链表倒数第N个节点——dummy节点与双指针第三道选取的是“删除链表的倒数第N个节点”。在 leetcode 上对应的题号是 19属于中等难度的高频题。它考察的核心是一次遍历情况下怎么只用一个指针协调好前后距离以及头节点可能被删除时怎么让代码统一处理。4.1 为什么要用双指针而不是两次遍历最简单直接的方法是先遍历一遍链表得到链表总长度 L那么倒数第N个节点就是正数第 L-N1 个节点再走第二遍把它删掉。这当然能过但面试官想看到的优化是能不能只遍历一遍可以而且方法很优雅。设置两个指针first 和 second初始都指向 dummy 头节点。先让 first 指针向前走 N1 步然后 first 和 second 以相同速度一起走。当 first 走到链表的末尾nullptr时second 恰好位于要删除节点的前一个节点。这时执行second-next second-next-next就完成了删除。这里有一个细节为什么 first 要先走 N1 步而不是 N 步因为我们需要 second 停在“待删除节点的前一个节点”上。如果 first 先走 N 步那么当 first 到末尾时second 正好停在待删除节点上你还需要额外的 prev 指针才能完成删除。先走 N1 步能让 second 天然指向待删除节点的前一个节点代码更简洁。4.2 dummy 节点省掉了最恶心的边界判断如果链表是 [1,2] 让你删倒数第2个节点删完应该得到 [2]。头节点1被删了那返回值就不能再是原来的 head 了得返回 head-next。不处理的话很多人会在这类边界 case 上翻车。解决办法就是在真正的头节点之前加一个哨兵节点 dummy把整个链表变成 dummy - head - ...。这样即使要删的是原头节点dummy 的下一个节点还是能正常更新最后你只需要返回 dummy-next 就行完全不需要关心头节点有没有被删。ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy new ListNode(0); dummy-next head; ListNode* first dummy; ListNode* second dummy; // first 先走 n1 步 for (int i 0; i n; i) { first first-next; } // 同步前进 while (first ! nullptr) { first first-next; second second-next; } // 删除倒数第 n 个节点 ListNode* target second-next; second-next second-next-next; delete target; // C 记得释放内存 return dummy-next; }这里还有两个容易忽略的小问题。第一个是for循环里走 N1 步时如果链表长度刚好等于 N比如链表长度是2N也是2删除倒数第2个节点那么 first 先走3步会走到 nullptr 吗不会因为 first 从 dummy 出发走 3 步刚好到 nullptr 前面的最后一个节点再往后才是 nullptr。你仔细数一下dummy - node1 - node2 - nullptr从 dummy 起步走一步到 node1走两步到 node2走三步到 nullptr。所以这里 for 循环次数是i n当 n2 时循环3次first 正好停在 nullptr然后 while 循环直接跳过second 保持在 dummy删除 dummy-next也就是原链表第一个节点逻辑完全正确。第二个是内存释放。C 的链表操作需要手动管理内存删除节点后要用delete释放掉否则会有内存泄漏。虽然刷题平台一般不检查这个但你写生产代码或者和面试官讨论的时候能主动说出“记得 delete”会很加分。Python 版本需要注意的点不同Python 没有指针但有引用同样可以用双指针和 dummy 节点。不同之处在于你不需要手动释放内存不需要 delete所以代码更清爽def removeNthFromEnd(head: ListNode, n: int) - ListNode: dummy ListNode(0) dummy.next head first dummy second dummy for _ in range(n 1): first first.next while first: first first.next second second.next second.next second.next.next return dummy.next4.3 延伸快慢指针在查找场景里的通用性删除倒数第N个节点这个“双指针先走N步再同步移动”的手法其实是一个通用公式可以延展到很多场景。比如“找链表中间节点”一个 fast 指针每次走两步一个 slow 指针每次走一步当 fast 走到末尾时slow 正好在中间。再比如“判断链表是否成环”本质上也是同一套指针体系。所以你看这三道题虽然各自独立但内里的核心套路是高度统一的先是 dummy 节点解决边界再是双指针制造距离差最后是空指针检查兜底。我把这三个要素背熟之后遇到别的链表题心里就有底了。5. 实操中的常见坑与调试技巧链表题的坑非常固定踩过一次以后记住了下次就不会再犯。我把这些年见到的、自己踩过的高频坑汇总成一个速查表方便你复习常见问题出现原因解决方案与检查思路空指针异常访问了 nullptr 的 next 或 val任何node-next使用前先保证 node 不为空涉及快指针时还要保证fast-next不为空链表断连后半部分丢失修改 next 之前没有保存后继节点养成习惯改指针之前先想“原来的下一个节点还在不在我的手里”头节点丢失删除头节点或反转后没更新头引用使用 dummy 节点或记住永远更新 head 变量的时机形成环程序死循环反转或删除时把某个节点的 next 指回了自己或前驱反转链表最后一定要把原头节点的 next 置为 nullptr调试时加一个步数上限返回了错误的“头”反转后返回了原来的 head反转链表循环结束后的 prev 才是新头删除头节点时用 dummy-next除了这些调试链表题有一个非常好用的方法画图。很多人一看到指针就头晕是因为只在脑子里凭空想象。我的建议是找一支笔一张纸或者用白板把所有节点画成方框next 画成箭头然后每执行一行代码就在图上走一遍。我面试候选人的时候如果一个人能在白板上把链表的图画清楚代码基本不会有大问题。另一个实操技巧是打印遍历。你可以稍微写一个辅助函数把链表的节点值依次打印出来在关键操作前后各打印一次立刻就知道有没有断链、有没有成环。对于环检测题打印时要加一个步数限制比如最多打印20步防止死循环把终端刷爆。6. 调试与追溯三道题一网打尽后的下一步写到这里三道题讲完了单链表反转教你三指针法和递归思维环检测与环入口带你从快慢指针到数学推导删除倒数第N个节点则展示了 dummy 节点和双指针配合的威力。它们合起来几乎覆盖了链表面试里八成以上的考点。我个人在实际带人的过程中体会最深的一点是链表题千万别背一定要动手画、动手写。你可以看完题解以后合上屏幕从零开始自己写一遍。第一遍可能憋很久、或者写出各种 bug这太正常了。等你能在三五分钟内把这三道题默写出来并且能把为什么不这么写就会错的原因讲明白你的链表基本功就真的过关了。最后再分享一个小技巧这三个算法背后的“双指针”“三指针”“哑元节点”不是链表独有数组、字符串、树的很多问题也用得上。你可以尝试用一个通用的“双指针框架”去重新看一遍你刷过的题会发现很多题解的开头都会长得很像。理解了这一层你就不只是在刷三道题而是建立了一套属于自己的算法解题框架。这篇文章的代码片段C 和 Python 版本我都给了你可以都用自己熟悉的语言跑一遍。跑通了以后推荐去刷同类型的题目验证一下环形链表 II、反转链表 II、两两交换链表中的节点、删除排序链表中的重复元素。这几道题看起来各不相同但底层套路就是我们今天讲的这一套。练完它们你对链表操作的肌肉记忆就真正形成了。
