链表OJ十题全解：从虚拟头节点到快慢指针的实战指南

链表OJ四个字足够让刚学完链表概念的人心里发怵。数组题做多了大脑会默认“有下标万事大吉”而链表里节点全靠指针串在一起查一个节点要遍历一遍删一个节点要先记住前驱稍不留神就解引用了空指针代码直接崩溃。这篇笔记是对“链表OJ”这个专题做的完整归纳我会把初阶阶段出现频率最高的十道题一次讲完移除链表元素、反转链表、链表的中间结点、倒数第k个结点、合并两个有序链表、链表分割、回文链表以及环形链表判定、找环入口、链表相交。每道题都会给出完整可跑的代码并把思路、复杂度、坑点交代清楚。适合刚学完链表准备刷题的同学也适合期末复习或者求职面试前快速过一遍的人。1. 链表OJ到底在考什么先把话说明白链表题考的不是“你会不会遍历链表”而是三个能力。第一是指针操作。链表的增删改查本质上就是改指针的指向。你觉得逻辑全对代码写出来却总是“差点意思”多半是改变指向的顺序出了问题。最典型的例子就是反转链表三行代码里有一条赋值顺序不对结果就完全不一样。第二是边界条件。链表题最容易翻车的地方不是核心思路而是各种边界空链表、只有一个节点、删除头节点、k的值比链表长度还大、偶数个节点找中间位置……这些情况稍微漏一个OJ上就会显示答案错误或者运行时直接崩溃segment fault。第三是内存管理。用C写链表题malloc出来的节点要用free还回去。至少三种情况会被判错忘了释放被删除的节点、忘了释放临时的dummy节点、在大量测试用例下内存越界。OJ系统是无情的本地跑得好不代表提交能过因为很多问题只有在严格的评测环境下才会暴露出来。这里还要强调一个认知链表题在逻辑上往往比数组题简单但代码上的出错率高得多。数组题的bug大多是“算错下标”链表题的bug则集中在“空指针解引用”和“while死循环”两类。你心里装着这个分类调试的时候就能快速缩小范围。2. 开写之前先建立两个底层思维这两个思维贯穿后面所有题目我先单独拿出来讲清楚。2.1 虚拟头节点把删头节点变得和其他位置一样在链表里删除节点很多人的第一版代码长这样如果要删的是头节点直接head head-next如果要删的是中间节点要先找到前驱 prev再prev-next cur-next。你会发现头节点和中间节点要分开写if 套 if代码又长又容易漏。解决办法就是虚拟头节点dummy node。自己malloc一个不存有效数据的节点让它的 next 指向真正的头节点。这样原链表里每个节点都有前驱了删除逻辑可以统一写成prev-next target-next;不用再单独判断“是不是头节点”代码量直接砍掉一半。这里有两个容易被忽略的细节用C写的时候dummy是malloc出来的函数结束前记得free掉否则每次调用都会泄漏一点内存大量测试用例跑下来就会累积成越界错误。返回的是dummy-next而不是原来那个head变量。因为head可能已经被删了你手头那个栈变量早就不是有效头节点了。2.2 快慢双指针一次遍历解决一半问题链表没有随机访问能力想拿到“中间位置”“倒数第k个”“是否存在环”这类信息最优雅的办法是快慢双指针。所谓快慢指针就是两个指针同时从头出发快指针每次走两步fast fast-next-next慢指针每次走一步slow slow-next。快指针走到末尾时慢指针恰好停在链表的中部所以找中间节点、判断回文、检测环形链表全都靠它。找倒数第k个节点则换一种玩法先让快指针走k步然后两个指针同步前进快指针到末尾时慢指针的位置正好是倒数第k个。快慢指针的正确性来自步数差但真正要记住的是 while 循环的条件while (fast fast-next)必须同时判断fast本身和fast-next不为空否则快指针走两步时会对空指针解引用程序秒崩。这几乎是所有快慢指针题统一的标准写法背熟它。2.3 动手前先列边界条件我的习惯是不管题目多简单下笔之前先在草稿纸上写几行字空链表、单节点、双节点。再把题目语言翻译成具体边界比如删除元素题元素在头部、在中间、在尾部、值根本不存在。倒数第k个k等于链表长度、k比链表长度大。中间节点节点数为奇数、节点数为偶数。OJ题的大部分扣分点其实不在核心算法上而在这些边角料里。你愿意花两分钟把情况列清楚后面写代码就会自然带上保护判断而不是写完再回头补。这个问题想明白了刷题效率能提升一倍。3. 七道入门必刷题逐题拆解下面这七道题难度从一颗星到三颗星按我推荐的顺序刷下来链表的基本功就稳了。每道题我都先讲思路再给代码最后说坑。3.1 移除链表元素题目要求删除链表中所有值等于给定 val 的节点返回新链表的头节点。这是虚拟头节点最典型的应用场景。思路用一个 prev 指针遍历每次检查prev-next的值是否需要删除。如果是把prev-next指向待删节点的 next并 free 掉待删节点如果不是prev 正常前进。struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode* dummy (struct ListNode*)malloc(sizeof(struct ListNode)); dummy-next head; struct ListNode* prev dummy; while (prev-next) { if (prev-next-val val) { struct ListNode* toDelete prev-next; prev-next toDelete-next; free(toDelete); } else { prev prev-next; } } struct ListNode* newHead dummy-next; free(dummy); return newHead; }时间复杂度O(n)空间复杂度O(1)。注意我free的是待删除的节点而不是prev。很多初学者图省事写成prev-next prev-next-next功能没错但被跳过的节点没有free在C的OJ评测里会被判为内存泄漏。3.2 反转链表题目要求把整条链表反序返回新的头节点。核心是三个指针的配合prev记录前驱cur记录当前节点next先保存cur的下一个节点。为什么必须先把 next 存下来因为一旦执行cur-next prevcur 原来指向的后半段链表就找不到了。所以顺序必须是先保存后面的节点再改当前指向最后整体平移。struct ListNode* reverseList(struct ListNode* head){ struct ListNode* prev NULL; struct ListNode* cur head; while (cur) { struct ListNode* next cur-next; cur-next prev; prev cur; cur next; } return prev; }这是链表题里出的最多的一道没有之一。面试官经常在此基础上变形反转前n个节点、反转链表中的一段、每k个一组反转。原理全是这一套三指针平移先把基础版想透再说变形。3.3 链表的中间结点题目要求给定头节点返回链表的中间节点。偶数个节点时返回第二个中间节点比如长度为4返回第3个节点。快慢指针一次遍历就能拿到struct ListNode* middleNode(struct ListNode* head){ struct ListNode* slow head; struct ListNode* fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; } return slow; }这个 while 条件要特别记牢fast-next必须一起判断。当链表中只有一个节点时fast-next是 NULL如果不判断下一轮访问fast-next-next就变成了对空指针解引用。复杂度O(n)时间O(1)空间。顺便说一句这个函数是后面回文链表题的前置操作。3.4 链表中倒数第k个结点经典题。思路是双指针拉开距离快指针先走k步然后两个指针同步前进快指针到末尾时慢指针正好指向倒数第k个节点。struct ListNode* getKthFromEnd(struct ListNode* head, int k){ struct ListNode* fast head; struct ListNode* slow head; while (k--) { if (fast NULL) return NULL; fast fast-next; } while (fast) { fast fast-next; slow slow-next; } return slow; }最容易踩的坑是 k 大于链表长度。快指针还没走完k步就遇到了 NULL此时必须直接返回 NULL否则下一轮会对空指针解引用。另一种标答是先遍历一遍数出长度 n再走 n-k 步思路更直观但要遍历两次双指针版只遍历一次更接近面试官想听到的答案。3.5 合并两个有序链表题目要求把两个升序链表合并成一个新的升序链表。用 dummy 节点加一个 cur 游标每次把值更小的节点接到 cur 后面。struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){ struct ListNode* dummy (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* cur dummy; while (l1 l2) { if (l1-val l2-val) { cur-next l1; l1 l1-next; } else { cur-next l2; l2 l2-next; } cur cur-next; } cur-next l1 ? l1 : l2; struct ListNode* newHead dummy-next; free(dummy); return newHead; }核心技巧在收尾那一行cur-next l1 ? l1 : l2。当某个链表走空了另一个链表剩余部分直接整段接上不需要一个节点一个节点地遍历。这比很多人习惯的“再把剩余节点while循环接上”要简洁得多而且不容易漏。原地合并空间O(1)时间O(nm)。3.6 链表分割题目描述给定一个链表和一个值 x把所有小于 x 的节点排在大于等于 x 的节点之前且保持原来的相对顺序不变。思路把原链表拆成两条临时链表一条收集小于 x 的节点一条收集大于等于 x 的节点最后把两条接起来。每条临时链表都带一个 dummy 节点方便操作。struct ListNode* partition(struct ListNode* head, int x){ struct ListNode* lessDummy (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* greaterDummy (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* less lessDummy; struct ListNode* greater greaterDummy; struct ListNode* cur head; while (cur) { if (cur-val x) { less-next cur; less less-next; } else { greater-next cur; greater greater-next; } cur cur-next; } greater-next NULL; less-next greaterDummy-next; struct ListNode* newHead lessDummy-next; free(lessDummy); free(greaterDummy); return newHead; }这里的关键坑点在于大值链表的尾节点的 next 一定要置为 NULL。否则它可能还指向小值链表末尾的某个节点两条链表一接直接形成一个环提交上去就会超时评测系统判断为死循环。这个题是面试常考的因为它考察的不只是能不能写出代码更考察你有没有意识到成环问题。3.7 链表的回文结构判断一个链表是不是回文正着读和反着读一样。比如 1-2-3-2-1 是回文1-2-2-1 也是。用数组收集所有值再判断当然能做但面试通常要求空间O(1)。三步走用快慢指针找中间节点反转后半段链表从两端同时向中间遍历比较只要有一处不同就不是回文。bool isPalindrome(struct ListNode* head){ if (!head || !head-next) return true; struct ListNode* slow head; struct ListNode* fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; } struct ListNode* prev NULL; struct ListNode* cur slow; while (cur) { struct ListNode* next cur-next; cur-next prev; prev cur; cur next; } struct ListNode* left head; struct ListNode* right prev; while (right) { if (left-val ! right-val) return false; left left-next; right right-next; } return true; }这里用 right 作为循环终止条件而不是 left。原因是反转后半段之后后半段是从原来的后半段头一路指回中间的right 这条链的终点是 NULL而 left 这一侧可能还比 right 多一个节点奇数长度场景。如果以 left 为准就会访问到反转区之外越界。如果面试官要求不改动原链表比较完把后半段再反转一次接回去即可。4. 两道进阶题环形链表与相交链表入门七道题做完再上两道“准进阶”题。它们在逻辑上绕一个弯但用的还是底层思维。4.1 判断单链表是否带环经典题。用快慢指针如果有环快指针会先进入环并在环里转圈慢指针进入环后两者最终一定会在某个节点相遇。依赖一个朴素的事实在环内快指针相对于慢指针每次多走一步所以不可能永远错过。bool hasCycle(struct ListNode *head){ struct ListNode* slow head; struct ListNode* fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) return true; } return false; }输入链表可能是带环的如果 while 条件写错就可能在环里无限循环OJ 直接报超时。另外一个容易被问到的细节为什么快指针一定能追上慢指针因为在环内两指针的距离差每次减1环长有限最多走不到一圈就能追上不存在“跳过去”的可能。4.2 找到环的入口节点在判断有环的基础上再找环的入口这才是环形链表的完整考法。先推导。设头节点到环入口的距离为 a环入口到相遇点的距离为 b相遇点继续走到环入口的距离为 c环长 L b c。慢指针走的路程是 a b快指针走的路程是 a b nL。快指针速度是慢指针的两倍所以a b nL 2(a b) → a b nL → a nL - b当 n 1 时a L - b c。也就是说从头节点出发的指针和从相遇点出发的指针各自每次走一步最终会在环入口相遇。n 大于1的情况等价于在环里多绕几圈结论不变。struct ListNode *detectCycle(struct ListNode *head) { struct ListNode* slow head; struct ListNode* fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) break; } if (fast NULL || fast-next NULL) return NULL; struct ListNode* ptr head; while (ptr ! slow) { ptr ptr-next; slow slow-next; } return ptr; }网上很多人只记住了“相遇后从头走一个指针再相遇就是入口”却说不清为什么。面试时把这个等式写出来立刻就能和背答案的人拉开差距。4.3 求两个链表的第一个相交节点两个单链表相交是指它们从某个节点开始共用同一批节点形状像字母Y。题目要求返回第一个相交节点。最直接的方法是算长度差分别遍历两个链表得到长度 n1、n2长链表先走 |n1-n2| 步然后两个指针同步走第一个相等的位置就是交点。更简洁的写法是双指针交替走struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { if (headA NULL || headB NULL) return NULL; struct ListNode* pa headA; struct ListNode* pb headB; while (pa ! pb) { pa pa ? pa-next : headB; pb pb ? pb-next : headA; } return pa; }为什么可行两个指针都相当于走了链表A加链表B的总长度。两条链表相交时pa 和 pb 会在某一步同时到达交点不相交时它们最后会同时走到 NULL循环自然结束。网上常把这个叫“换头走法”本质上是把两条链表的长度差抹平了。5. 链表调试实战从崩溃到AC算法题写出来只是第一步真正花时间的是调试。链表题的调试有自己的套路和普通程序不太一样。5.1 画图是你最好的调试工具链表题最忌讳空想。我在本地跑每道题之前一定先在草稿纸上画一个三节点的链表把每个节点的地址和值写出来再手动模拟指针的变化。画着画着就能发现很多隐藏问题反转链表里的赋值顺序、链表分割里尾节点是否置空这些都是画图能一眼看出来的。一个实用的辅助函数在本地测试时打印链表内容void printList(struct ListNode* head){ int count 0; while (head count 20) { printf(%p:%d - , head, head-val); head head-next; count; } printf(NULL\n); }count 上限的作用是防止死循环链表把控制台刷爆调试环形链表时尤其有用。建议把它放进你的常用代码片段里每道题本地测试都先跑一遍。5.2 必测的六组用例每次交代码前至少要把下面六组用例在本地过一遍空链表head 为 NULL函数不崩且返回合理值。单节点链表很多 while 条件的问题在这里暴露。双节点链表偶数长度场景检查 fast-next 的边界。值全部相同删除题里所有节点都被删光应返回 NULL。极端参数k 大于链表长度、x 比所有节点值都小或都大。长链表压力测试构造 5000 个节点的用例验证时间和内存。5.3 常见崩溃与超时的定位方法段错误Segmentation fault十有八九是对 NULL 解引用。在可疑语句前加 printf 打印指针或者用调试断点看崩在哪一行再检查那一行访问了哪个指针。超时Time Limit Exceeded链表题超时基本都是死循环。检查 while 条件是否保证了每一步都让指针向内移动特别留意快指针走两步之前是否判断了 fast-next。答案错误先把返回头节点的逻辑重新看一遍。很多链表题会改动原链表头节点可能已经变化这时候返回 dummy-next 是最稳的。6. 高频报错与避坑速查表把常见问题整理成一张表建议截图保存每次提交前对照自查报错现象常见原因排查方向段错误对 NULL 解引用如 fast-next-next 而 fast-next 为空检查所有 while 条件补上 fast 与 fast-next 判空超时while 条件不推进指针或链表成环后无限循环确认每次循环都有指针移动链表分割题检查大值链尾是否置空答案错误头节点变化后返回了旧的 head 变量统一返回 dummy-next内存泄漏malloc 后没有 free删除的节点和 dummy 都要 free只过一半用例边界条件没覆盖如 k 大于长度、空链表对照必测六组用例逐条验证三条血泪经验是我自己踩过无数次坑之后总结的写完代码先把所有“-”扫一遍凡是可能为 NULL 的地方优先补保护。涉及节点删除或反转时先保存即将丢失的指针再改变指向顺序永远不能反。提交前在一个最小用例上手动模拟一遍完整流程不要写完直接交。我个人的体会是链表OJ考验的其实不是智商而是你有没有养成“边界优先、画图先行”的习惯。一开始我总急着看答案后来耐下性子每道题先画图再手写正确率明显上来了。把这组题目吃透之后后面学树的遍历、图的邻接表你会发现很多操作本质上还是链表那套指针思维。刷题平台上的题目外观再怎么变底层其实就是三件事虚拟头节点、快慢双指针、边界条件。把这三件小事磨利了链表OJ这座山你就稳稳当当地翻过去了。