期末复习的时候我被数据结构里的单链表狠狠上了一课。数组题写顺手之后一碰到链表就发蒙明明逻辑结构是一样的但代码就是绕不过来。后来痛定思痛把常见的单链表OJ题逐一复盘才发现这类题目其实有规律可循。单链表在数据结构里是一个承上启下的角色向上承接线性表的逻辑结构向下为栈、队列的链式存储做铺垫往后学二叉树、图的邻接表也都依赖链表操作。而OJ题是检验理解程度最直接的方式刷OJ等同于把知识应用在真实题目里连出错方式和工程环境都非常接近。这篇文章就把我复盘单链表OJ题的过程和思路整理出来。内容包括单链表OJ题到底在考什么、三类高频套路、必刷题型的代码细节、易错点与Bug排查、以及我个人沉淀的刷题方法论。无论你是准备期末考试、考研复试还是面试前突击数据结构这篇文章都能给你一个相对完整的参考框架。1. 复盘思路单链表OJ题到底在考什么1.1 从“逻辑结构”到“物理结构”的思维切换数组写起来舒服是因为它自带“连续内存”这个天然优势。a[i1]就是a[i]的下一个元素不用操心地址怎么找。但链表不是这样。单链表的每个节点在内存中分散存放节点之间靠next指针串联你手里拿着一个头指针就只能从头往后走想回头就得重新遍历。所以单链表OJ题真正考的不是“会写增删改查”而是“能不能在只能看到当前节点的情况下正确操作多个指针完成结构修改”。这种操作方式和数组思维是反过来的很多人栽跟头就是思维没切换过来。我复盘时的一个体会是写单链表题必须先接受“节点之间是线性的、方向唯一的”这个前提。你不能像数组那样随意跳转也不能指望编译器帮你保存断链前的旧状态所有需要“回溯”的信息都必须自己动手用变量存下来。1.2 三类高频套路双指针、哑节点、递归刷多了之后会发现单链表OJ题的解法虽然千变万化核心套路就三类。第一类双指针。最经典的是快慢指针一个指针每次走两步一个每次走一步。它可以用来求链表中点、判断链表是否有环、找环的入口还能通过“先让一个指针走k步再同步走”的方式找倒数第k个节点。快慢指针的本质是利用步速差产生位移差让两个指针在某个特定位置相遇或者让慢指针刚好落在目标位置。第二类哑节点。哑节点是一个不存储有效数据的虚拟头节点放在真实头节点前面。有了它所有节点都能用同一种逻辑处理不需要为“操作头节点”单独写分支。删除头节点、合并链表、插入节点、按条件拆分链表这类头节点会变动的题目哑节点几乎是标配。第三类递归。链表天然是递归结构一个节点后面还跟着一个子链表所以很多链表题用递归写特别简洁比如反转链表、合并两个有序链表、两两交换相邻节点。这三类套路不是孤立的很多题目要组合使用。比如删除链表的倒数第N个节点既可以用双指针也可以用哑节点加双指针再比如合并两个有序链表既可以用哑节点迭代也可以用递归。先掌握单一套路再尝试组合是刷题效率最高的路径。2. 必刷题型拆解从示例到实现细节2.1 反转链表双指针迭代和递归两种写法反转单链表是单链表OJ里最基础也最核心的题网上有句话叫“反转链表是链表的乘法口诀表”不练熟这道题后面很多题都会磕磕绊绊。题目要求输入1-2-3-4-5输出5-4-3-2-1。迭代法用三指针struct ListNode* reverseList(struct ListNode* head) { struct ListNode *pre NULL, *cur head, *tmp; while (cur ! NULL) { tmp cur-next; // 先保存后继节点 cur-next pre; // 当前节点指向前一个节点 pre cur; // 前驱指针前进 cur tmp; // 当前指针前进 } return pre; }拆开看tmp保存当前节点的下一个节点防止断链后丢失cur-next pre是让当前节点指向前一个节点pre cur和cur tmp分别让前驱指针和当前指针前移。循环结束时cur为NULLpre正好落在原链表最后一个节点上也就是反转后的新头节点。这里最关键的细节是先保存再改指向。如果不先保存tmp第一行执行完之后原链表的下一个节点就找不到了。递归法也要会写struct ListNode* reverseList(struct ListNode* head) { if (head NULL || head-next NULL) { return head; } struct ListNode* newHead reverseList(head-next); head-next-next head; head-next NULL; return newHead; }递归想明白不容易我当时靠画图才理解。把head-next当成一段已经反转好的子链表head要接到这段子链表的尾部。而head的下一个节点反转后变成了子链表的最后一个节点所以head-next-next head就是把head接到子链表尾部最后head-next NULL收尾。2.2 链表中点快慢指针的边界条件题目给定头节点head返回链表的中间节点。如果有两个中间节点返回第二个。示例1-2-3-4-5返回31-2-3-4-5-6返回4。struct ListNode* middleNode(struct ListNode* head) { struct ListNode *slow head, *fast head; while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; } return slow; }快慢指针的逻辑是快指针走两步慢指针走一步快指针到终点时慢指针刚好走了一半。循环条件里的两个判断要重点说明。如果链表有偶数个节点比如6个节点快指针的移动路径是1-3-5-NULL走到NULL时慢指针正好在4也就是第二个中间节点。如果只写fast ! NULL没有问题但如果不写fast ! NULL只写fast-next ! NULL快指针在最后一轮会变成NULL再判断fast-next就是空指针解引用程序直接崩。很多人会问为什么要返回第二个中间节点而不是第一个这是题目约定按题来就行。如果以后遇到要求返回第一个的情况只需要调整循环条件让快指针少走一步或者让慢指针的移动时机推迟一步。2.3 删除链表的倒数第N个节点双指针加哑节点题目给定一个链表删除倒数第n个节点并且返回头节点。这道题比前两个稍复杂需要同时用到双指针和哑节点。思路是创建哑节点dummydummy.next head。先用一个指针fast从头节点开始走n步然后slow从dummy开始fast和slow同步前进。当fast走到NULL时slow正好停在待删除节点的前一个节点最后执行slow-next slow-next-next就完成了删除。struct ListNode* removeNthFromEnd(struct ListNode* head, int n) { struct ListNode dummy; dummy.next head; struct ListNode *fast head, *slow dummy; for (int i 0; i n; i) { fast fast-next; } while (fast ! NULL) { fast fast-next; slow slow-next; } slow-next slow-next-next; return dummy.next; }为什么要用哑节点因为如果要删除的恰好是头节点没有哑节点的话删除后需要单独返回head-next逻辑上要多写分支。有了哑节点slow始终是目标节点的前一个节点删除操作统一为一行代码。这里还有一个细节fast先走n步时如果n等于链表长度fast最终为NULL此时slow还在dummy位置删除的是头节点dummy.next会变成原head的下一个节点逻辑完全正确。2.4 合并两个有序链表哑节点加尾插法题目将两个升序链表合并成一个新的升序链表。迭代法struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { struct ListNode dummy; struct ListNode* tail dummy; dummy.next NULL; while (list1 ! NULL list2 ! NULL) { if (list1-val list2-val) { tail-next list1; list1 list1-next; } else { tail-next list2; list2 list2-next; } tail tail-next; } tail-next (list1 NULL) ? list2 : list1; return dummy.next; }这个思路类似“织毛衣”两个链表像两股线比较每个节点的值把较小的那个接到tail后面然后移动对应指针。哑节点在这里避免了“第一个节点从哪来”的问题。while循环结束后一定有一个链表还剩节点这时候不需要再逐个比较直接把剩余链表接到tail后面就完事。这行代码很容易忘忘了就会丢掉一部分数据。2.5 相交链表双指针走对方的路题目找到两个单链表相交的起始节点要求时间复杂度O(mn)空间复杂度O(1)。这道题的解法非常巧妙让两个指针分别从两个链表头出发同时向后移动。当指针走到自己链表的末尾时跳到另一个链表的头部继续走。如果两个链表相交这两个指针一定会在相交节点相遇如果不相交它们会同时走到NULL。为什么能相遇设链表A在相交前的长度为a链表B在相交前的长度为b公共长度为c。指针pA先走a c然后从B头开始走b指针pB先走b c然后从A头开始走a。两者到达相交节点的总步数都是a c b所以必然相遇。这一题不需要额外空间理解之后对“双指针不只用于快慢”会有更直观的认识。3. 易错点与边界条件这些坑最容易挂3.1 空指针解引用几乎所有崩溃的来源链表OJ题提交后最常见的运行时错误就是段错误而段错误多半来自空指针解引用。常见的空指针场景有三种。一是head为NULL时仍然访问head-next。二是快慢指针中快指针已经为NULL循环体里还在判断fast-next-next。三是合并两个有序链表时其中一个链表为空还去访问它的val。养成一个习惯写循环和递归时先判断指针是否为NULL。宁可多一次判断也不要让程序崩溃。如果判断条件里包含了“不为空”的要求优先把判空写在前面利用C语言“短路求值”的特性后边的表达式不会被执行。3.2 指针丢失最隐蔽的逻辑错误指针丢失是链表题里最经典的逻辑错误。典型的场景是删除节点时直接用目标节点的next覆盖前驱节点的next但后续代码还继续访问那个节点结果发现链表“断”了。核心口诀是“先存后改”。在修改任何一个next指针之前先把要跳过的节点或者后继节点保存到临时变量里。只要遵循这个原则绝大多数指针丢失问题都不会发生。我见过很多同学在纸上推演没问题一上机就丢指针原因就是跳过了保存步骤。代码写得快反而在错误的方向上跑得更快。3.3 尾节点next没有置空野指针与死循环构造链表时最后一个节点的next必须置为NULL这是链表操作的底线。很多新手忘了这一步OJ遍历时会一直走下去不是死循环就是越界。反转链表时也要特别注意原来的head会成为新链表的尾节点必须把head-next置为NULL。如果忘了反转后的链表会指向一堆随机地址打印结果时就会出现尾部多出一串乱码甚至崩溃。3.4 递归深度引发的栈溢出递归解法代码短思路清晰但有一个现实的坑递归深度和链表的长度成正比。OJ的数据规模如果给到几万甚至几十万节点递归很容易爆栈。我建议把递归当成“理解工具”而不是“提交工具”。平时练习时可以用递归理解解题本质提交OJ或写工程时优先用迭代解法。4. 常见问题与Bug排查实录4.1 为什么反转链表会死循环有一次帮同学排查反转链表的代码他的写法是while (cur ! NULL) { cur-next pre; pre cur; cur cur-next; }乍看很像标准写法但运行起来直接卡死。问题出在第一行cur-next pre执行后原来的下一个节点就丢了。第三行的cur cur-next本质上是访问了已经被改成pre的节点于是cur从某个节点又回到了前一个节点形成循环。如果发现自己写的代码运行很久都没结果优先怀疑循环里指针是否回到了已访问过的位置。最简单的排查方式是把每一步的指针值打印出来或者直接在纸上画一遍。4.2 快慢指针越界访问求链表中点时循环条件必须是while (fast ! NULL fast-next ! NULL)。不少人为了简化条件写成while (fast-next ! NULL)在节点数为奇数时能跑对在节点数为偶数时就会崩。原因不复杂。偶数节点时快指针会移动到NULL上再去判断fast-next等于对NULL解引用。这类错误本地不一定能复现因为某些编译器对空指针访问的处理方式不同但OJ上基本必挂。遇到快慢指针题循环条件直接照抄“双判断”模板不要自己发挥。4.3 合并链表时丢失剩余部分合并两个有序链表时如果忘记拼接剩余链表返回的结果会缺少较长链表的后半段。问题代码长这样while (list1 ! NULL list2 ! NULL) { // 逐个比较... } return dummy.next;只要两个链表长度不同就一定有一个非空链表没接完。正确做法是在return之前加一行tail-next (list1 NULL) ? list2 : list1;这行代码相当于把剩下的整段一次接上是合并类题目的标准收尾动作。4.4 本地调试三板斧打印、画图、最小样例OJ不给你打印日志的机会所以调试都在本地完成。我刷链表题时最常用的三板斧第一打印法。在关键节点打印当前指针指向的值观察指针移动是否符合预期。比如反转链表时在每次循环开始和结束打印pre、cur的值很快就能看出哪一步出了问题。第二画图法。链表题没有画图解决不了的bug。我自己的习惯是把链表画成方框加箭头每到一步就标出新指针的指向画完基本能定位问题。第三最小样例法。不要一开始就用长链表测试。先用空链表、单节点链表、双节点链表、三节点链表分别跑绝大多数边界问题在最小样例阶段就能暴露。异常表现常见原因解决办法程序卡死无输出反转链表环节未保存nextcur回到旧节点用tmp保存后继再改指向段错误/运行时错误空指针解引用如fast为NULL仍判断fast-next循环条件同时判fast和fast-next输出结果缺一段合并链表结束后未拼接剩余链表补上tail-next 剩余链表头尾结点后出现乱码尾结点next未置NULL反转后把新尾结点next置NULL本地正常提交出错递归过深导致栈溢出改用迭代写法5. 从刷题到内化建立属于自己的链表模板5.1 刷题节奏推荐如果你正在准备复试或者面试我建议按下面的顺序练手。第一阶段做反转链表和两两交换节点熟悉指针操作第二阶段做链表中点、倒数第k个节点、环形链表熟悉双指针第三阶段做合并两个有序链表、删除倒数第n个节点、相交链表熟悉哑节点与组合套路。每道题先自己做一遍再对照标准答案记录卡住的点。过几天再做一遍如果还能顺畅写出来说明真的掌握了。5.2 把套路固化成模板强烈建议把三类套路整理成自己的模板。比如哑节点模板永远是struct ListNode dummy; dummy.next head; struct ListNode* cur dummy; // 操作... return dummy.next;双指针模板struct ListNode *slow head, *fast head; while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; }递归模板if (head NULL || head-next NULL) { return head; } struct ListNode* newHead 递归(head-next); // 调整当前节点... return newHead;模板的作用不是让你背题而是减少重复劳动。拿到新题先想能不能套双指针能不能用哑节点能不能用递归想清楚之后再动手写代码准确率会高很多。5.3 链表基础对其他数据结构的意义单链表刷透了后面学二叉树、图会轻松不少。二叉树的左孩子右孩子在存储上就是两个指针域图的邻接表本质是数组加链表。链表里那套“先保存再修改”的思路放到树和图的操作中一样好用。所以花在单链表上的时间不是白费的它是整个数据结构学习路线里性价比很高的投资。我把这一轮复盘最大的体会放在最后。第一单链表OJ题不看代码量看指针意识第二凡是要修改next指针先保存后继第三写任何循环和递归都要先想空指针条件。这三个习惯比刷多少题都重要。另外有一个小技巧刷链表题时每次都在本地写一个打印链表的辅助函数用来快速验证结果。这个函数虽然简单但在调试时能省下大量时间比反复看代码效率高得多。单链表只是起点如果你能把这里的方法论带到后续的二叉树、排序算法、图算法里数据结构的学习会越来越顺。