很多人学数据结构前面的顺序表、单链表增删查改都写得顺一到“链表OJ”就开始怀疑自己。我见过不少同学课能听懂、增删接口也能写但面对在线判题平台上一道一道链表题就卡住要么空指针崩溃要么提交十几次都过不了要么代码看着没问题运行结果却总是差一个节点。链表OJ其实不是考“谁记得接口多”它考的是你能不能把链表的指针关系看明白把边界情况想全把思路画成图再落成代码。这篇笔记适合刚学完链表基础知识、准备开始刷题的人也适合之前刷得磕磕绊绊、想系统整理一遍的人。我会把链表OJ最常见的题型、解法思路、推导过程和踩坑经验一起整理出来当作一版随时能回来翻的笔记。1. 链表OJ到底在练什么先别动手想清楚这三件事很多人一看到链表OJ题第一反应是打开编译器直接写。真正高效的顺序其实是先画图再想边界最后才写代码。链表题目有一个共同点——代码量不大但只要你少考虑一个条件结果就是段错误或者死循环。它的难度几乎全部集中在“看不见”的地方所以动手之前先在脑子里把运行过程过一遍比盲目提交试错重要得多。1.1 画图能力决定你能不能动手链表跟数组最大的区别是数组的下标是连续的你知道当前下标就能直接访问下一个链表则完全依靠 next 指针每个节点都不知道自己的后继是谁除非你拿着头指针从头遍历。所以链表题的几乎所有操作归根结底都是“改变指针指向”而不是“移动下标”。做题时不画图等于蒙着眼睛开车。最典型的例子就是单链表反转。你打算让当前节点的 next 指向前一个节点问题是这一指当前节点原本的后继节点就找不到了。如果不先把 next 保存下来链表当场断成两截。这个“先保存后继再改指向”的思路画一遍立刻明白闭眼写就容易崩。我给初学者的建议是每道链表OJ题先在草稿纸上画三个节点模拟两三轮指针移动把每一轮每个指针分别指向哪里写清楚再动手写代码。这样看起来慢实际比自己反复调试要快得多。1.2 边界条件意识空链表、单节点、尾节点链表OJ最容易挂的不是算法而是边界。空链表、只有一个节点、只有两个节点、删除最后一个节点、找倒数第一个节点、链表有环、链表相交……每一种情况稍不注意就是空指针解引用或者直接死循环。数组题里你可能只需要关心 i n链表题里你至少要关心三件事当前节点是否为空、当前节点的 next 是否为空、指针移动之后会不会跳出链表。我自己整理笔记时有个习惯拿到一道题先把题目给的条件列表里的边界情况列在旁边。比如题目说“链表可能为空”那空链表的情况必须在所有测试里排第一个。然后想单节点和双节点的情况等这些在本地都能跑过再上 OJ 提交。边界条件如果都要靠判题系统反馈才知道刷题效率会非常低但如果你在本地主动构造这些输入反而能积累出很强的边界直觉。1.3 指针模型切断和重接链表OJ还会逼你建立一种“指针模型”head 是第一个节点的地址p-next 是下一个节点的地址修改 p-next 不会改变节点里的 val。如果你想让一个节点从 A 链表挪到 B 链表只需要让 B 的尾节点指向它再让 A 的前一个节点指向它的 next本质上就两个动作切断旧链接、重接新链接。带着这个模型去看题目会发现反转链表、分割链表、合并有序链表都是同一套动作的变体。你只需要关心两件事当前节点是谁它的 next 在改变之前还存在不存在。很多同学写链表题容易乱就是因为把注意力放在“结果长什么样”上而不是“每一步指针怎么跳”上。后面每个题型本质上都在反复训练这个模型。2. 反转链表迭代和递归两条路但同一个核心反转链表几乎是链表OJ里必考的第一道题。它看起来特别简单但迭代和递归两种写法都藏了不少细节。这道题如果能在不看答案的情况下独立写对说明你的链表指针基础基本过关了。2.1 迭代版本三指针穿针引线迭代反转的核心语句是每次把当前节点 cur 的 next 指向前一个节点 prev然后整体右移。但注意cur-next 一旦被修改原来 cur 后面的节点就找不到了所以必须在修改之前先把原后继保存下来。代码是这样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; // 移动 prev cur next; // 移动 cur } return prev; }你可以在草稿纸上画一个三段链表让 prev 一开始指向 NULLcur 指向头节点。第一轮把头节点 next 改成 NULL头节点就被“摘”下来了同时 prev 走到头节点位置cur 走到原第二个节点。第二轮第二个节点的 next 改成指向头节点链表第一段开始倒过来。如此循环到 cur 为 NULL 时prev 正好停在整个链表的最后一个节点上也就是反转后的新头。很多同学写错的地方有两个一是不先保存 next结果修改完 cur-next 之后循环里根本找不到后续节点二是循环结束返回 cur但 cur 此时是 NULL正确返回值应该是 prev。要记住反转链表的头节点永远是原链表的尾节点。2.2 递归版本从后往前改 next递归的代码更短但抽象程度更高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它后面的链表已经全部反转好了newHead 指向反转后的新头也就是原链表的尾节点。而 head 原本的后继节点 head-next现在正好是反转后链表的最后一个节点。所以需要让 head-next-next head把当前节点接回到反转链表的尾部再把 head-next 置空防止形成环。递归写法的常见错误是漏掉 head-next NULL。如果不置空最后一个节点可能还会指向原链表中的某个节点造成结果带环或者输出超长。递归反转虽然看起来优雅但初学阶段如果觉得难可以先只用迭代版本等理解了栈帧和回溯之后再来补递归。2.3 为什么看懂了答案自己写还是崩我见过很多同学看书看题解都懂一到自己写就卡住。原因通常是只记住了“步骤”没有真正验证指针顺序。反转链表最怕的就是在循环里“先改 next再保存 next”这个顺序错一步整段链表就断了。我的建议是把迭代版本循环内的四行代码按顺序背下来每行在做什么写在注释里然后自己画图推一遍。不要只看题解的最终代码要在草稿纸上把每轮循环的 prev、cur、next 三个指针的位置全部标出来。等你亲手画完三轮这类题基本上就不会再错了。3. 快慢指针全家桶从找中点到环入口链表OJ里有一个特别大的套路家族叫快慢指针。它用两个指针一个每次走一步另一个每次走两步通过速度差来达到“探测结构”的目的。找中间节点、找倒数第 k 个节点、判断链表是否有环、找环入口全都能用这一套思路解决。这个套路一旦掌握很多中等题就能直接降维。3.1 找中间节点快慢指针最基础的应用找链表中间节点的代码非常短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; }这里的逻辑是fast 的速度是 slow 的两倍当 fast 走到链表末尾时slow 正好在链表中间。问题是链表长度分奇偶两种情况链表有奇数个节点时fast 最后一次停在最后一个节点slow 会停在正中间链表有偶数个节点时fast 最终会走到 NULLslow 停在第二个中间节点上。很多题目需要的是“后半段的头节点”比如回文链表这时取第二个中间节点正好合适。如果你需要取偶数情况的第一个中间节点可以加一个虚拟头节点或者把循环条件改成 fast-next 和 fast-next-next但初阶阶段默认取第二个中间节点是最常见的直接用上面的代码就可以了。找倒数第 k 个节点也是同一个套路让快指针先走 k 步然后快慢指针一起每次走一步。快指针走到 NULL 时慢指针正好指向倒数第 k 个节点。但这里要额外处理链表长度小于 k 的情况struct ListNode* getKthFromEnd(struct ListNode* head, int k) { struct ListNode* fast head; struct ListNode* slow head; for (int i 0; i k; i) { if (fast NULL) { return NULL; // 链表长度小于 k } fast fast-next; } while (fast) { slow slow-next; fast fast-next; } return slow; }先走的 k 步本质上是在制造“偏移量”让两个指针之间始终保持着 k 个节点的距离。这样快指针到达 NULL 时慢指针距离末尾也是 k 步自然就是倒数第 k 个节点。3.2 判断是否有环跑得快的总会被跑得慢的追上环形链表的判断是快慢指针的高频应用之一。代码几乎和找中点一样只是多了一个相等判断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; }你可以想象两个人在环形跑道上跑步快的人速度是慢的人的两倍。只要跑道存在闭环快的人最终一定会从后面追上慢的人如果跑道没有闭环快的人会先到达终点 NULL循环直接结束。这个写法里有几个容易踩的坑循环条件必须同时判断 fast 和 fast-next因为 fast 每次走两步少了任何一个判断空链表或单节点链表都可能直接解引用空指针。另一个坑是相等判断必须放在移动之后不能在循环开头判断否则 slow 和 fast 初始都指向 head会被误判成有环。3.3 找环入口一个需要数学推导的经典问题判断有环之后题目通常会更进一步返回环的入口节点。这个问题的推导值得认真看一遍。假设头节点到环入口的距离是 a环入口到两个指针第一次相遇点的距离是 b相遇点继续走到环入口的距离是 c那么环的周长 L 就是 b c。slow 进环后走的路程是 a bfast 走的路程是 a b nL其中 n 表示 fast 在追上 slow 之前已经在环里多走了 n 圈。因为 fast 的速度是 slow 的两倍所以 fast 总路程等于 slow 总路程的两倍于是a b nL 2 * (a b) a b nL a nL - b a (n - 1)L c这个结果的含义是如果从链表头节点出发走距离 a同时从相遇点出发走距离 c也就是沿着环继续走到入口的距离两个指针会在环入口恰好相遇。因为 a 可以被拆成“n-1 圈完整的环”再加一段 c最终它们会落在同一个点上。所以代码的写法是先用快慢指针找到相遇点一旦相遇把一个指针拉回 head另一个留在相遇点两个指针都改成每次走一步再走一定步数后的相遇位置就是环入口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) { struct ListNode* p head; struct ListNode* q slow; while (p ! q) { p p-next; q q-next; } return p; } } return NULL; }3.4 快慢指针的常见翻车点快慢指针整体思路不难但细节很多我自己刷题时整理过几个高频翻车点。第一个是循环条件写成 while (fast-next)没有检查 fast 本身是否为空空链表直接崩。第二个是判环时先判断相等再移动导致初始状态就被误判为有环。第三个是有人为了加快速度把 fast 改成每次走三步甚至四步结果相对速度不再是 1反而可能跳过相遇点或者写出错乱结果。快慢指针最稳妥的设定永远是 slow 走一步、fast 走两步不要为了炫技乱改步长。4. 合并有序链表、相交链表、分割链表链表的“拼接艺术”如果反转链表练的是“指针方向”那合并、相交、分割这三类题练的就是“链表拼接”。它们都不是很难但特别容易在细节上出问题尤其是头节点不确定的情况怎么处理。4.1 合并两个有序链表哨兵节点解决头为空的问题合并两个有序链表的思路和合并两个有序数组很像两个链头同时开始谁的值小就取谁。但链表有一个麻烦新链表的头节点可能是 l1 的头节点也可能是 l2 的头节点写起来得提前判断。一个更简单的办法是用哨兵节点也叫 dummy 节点struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) { struct ListNode dummy; dummy.next NULL; struct ListNode* tail dummy; while (l1 l2) { if (l1-val l2-val) { tail-next l1; l1 l1-next; } else { tail-next l2; l2 l2-next; } tail tail-next; } tail-next l1 ? l1 : l2; return dummy.next; }哨兵节点最大的作用是让所有新节点插入的逻辑保持一致不需要在循环里判断“当前新链表是不是空的”。最后l1 和 l2 中一定有一个已经走到 NULL另一个剩余部分本身就是有序的直接让 tail-next 接上剩余链表即可。需要提醒的是这里没有 malloc 一个新的哨兵节点而是在栈上定义了一个局部变量 dummy。这样做不需要手动释放返回 dummy.next 也安全。如果你改用 malloc 创建哨兵节点记得在函数结束前 free 掉否则会有内存泄漏。4.2 相交链表用“走完对方的路”来消除长度差相交链表的意思是两个链表从某个节点开始后面的节点完全共享。求第一个相交节点最简单的做法是先算出两个链表各自的长度然后让长链表先走长度差再两个指针一起走第一个相等的节点就是交点。还有一种更巧妙的写法不需要先求长度而是让两个指针循环交替遍历两个链表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; }你可以想象两个指针分别从两个链表出发当某一个指针走到 NULL 时立刻跳到另一个链表的头节点继续走。这样做的效果是pA 和 pB 都走过了“A链表长度 B链表长度”的总路径长度差异被彻底抹平。如果两个链表相交它们会在某个节点碰上如果完全不相交它们最终会同时走到 NULL循环结束返回 NULL。这个解法的代码很短但它背后“用路径来抵消长度差”的思想值得多画几遍图。尤其是两个链表长度差特别大的情况纸上推一遍才能理解为什么两个指针最后能同步。4.3 分割链表拆成两个链表再拼回去分割链表一般长这样给定一个链表和一个值 x要求把所有小于 x 的节点放在所有大于等于 x 的节点前面并且保持原有的相对顺序。这个题不能简单排序因为题目要求每个区间的相对顺序不变。我的做法是维护两个哨兵链表一个装小于 x 的节点一个装大于等于 x 的节点。遍历原链表按值把每个节点尾插到对应的链表中最后把两个链表接起来struct ListNode* partition(struct ListNode* head, int x) { struct ListNode lessHead; struct ListNode greaterHead; lessHead.next NULL; greaterHead.next NULL; struct ListNode* ltail lessHead; struct ListNode* gtail greaterHead; struct ListNode* cur head; while (cur) { struct ListNode* next cur-next; // 先保存后继 if (cur-val x) { ltail-next cur; ltail cur; } else { gtail-next cur; gtail cur; } cur next; } gtail-next NULL; // 让大值链表正确收尾 ltail-next greaterHead.next; return lessHead.next; }这里有两个关键点。第一每次移动 cur 时必须先把 cur-next 保存下来因为你会把 cur 接到新链表上原链表的关系已经不存在了。第二最后必须让 gtail-next NULL否则尾节点可能还指向原链表后面的某个节点导致新链表成环或输出多了内容。这类“拆开再拼接”的题只要画出两个哨兵链表的接入过程其实比想象中简单。很多同学容易写错的地方恰恰是忘记在原链表里保存 next。5. 回文链表与排序链表组合题是真正的分水岭单点技巧刷熟之后就要开始接触组合题。组合题不会特别难但要求你把前面几类题型的技能串起来比如找中点、反转链表、合并链表。这类题很容易出现在课后练习里也很适合检验自己是不是真理解了每个基础操作。5.1 回文链表找中点 反转后半段 双指针比较回文链表要求判断一个链表是否前后对称比如 1 - 2 - 3 - 2 - 1 就是回文。数组的回文判断很简单从两边往中间比较即可但链表不能从后往前遍历所以常用技巧是先用快慢指针找到链表中点再把后半段链表反转最后从前半段头节点和反转后的后半段头节点同时开始比较。bool isPalindrome(struct ListNode* head) { if (head NULL || head-next NULL) { 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; }这段代码里slow 指向链表中间节点。如果是奇数长度的链表slow 正好在正中间反转后半段之后多比较一次中间节点也无妨如果是偶数长度的链表slow 指向第二个中间节点反转后半段之后正好能完成长度相等的两段比较。这个方法会破坏原链表结构不过大多数 OJ 题只关心返回值所以问题不大。如果面试要求不破坏原链表可以在比较完后再把后半段反转回去。5.2 排序链表用前面所有技巧做一次综合检验排序链表是个更进阶的组合题。它要求把链表排成升序常见解法是归并排序先找中点把链表拆成前后两半递归排序然后用归并两个有序链表的逻辑合并。这个过程会把快慢指针找中点和合并两个有序链表两个技巧同时用上是不错的综合训练。递归版的排序链表代码不长思想也清楚但因为每层递归都要重新用快慢指针找中点总复杂度仍然稳定在 O(n log n)。如果题目要求严格的 O(1) 额外空间那就得改成自底向上的迭代归并代码会复杂不少。初阶阶段不用一开始就死磕迭代版本先把递归版本理解透知道它用到哪些前面学过的技能就已经达到综合检验的目的了。6. 我的避坑清单链表OJ里那些“必挂”的写法这部分是我自己刷题和帮别人看代码时最常遇到的错误把它们整理成一张表方便复习的时候直接对照。6.1 最常犯的错误类型错误现象可能原因正确做法空链表直接崩溃循环里没有判断当前指针是否为空while 条件写成p p-next反转链表后丢了一半节点修改cur-next前没有保存后继先保存next再改指向判环对单节点链表误判相等判断写在了指针移动之前先移动再判断是否相等合并或分割后链表成环尾节点的 next 没有置 NULL拼接完成后主动tail-next NULL返回值总是 NULL反转后返回了cur而不是prev返回原链表的尾节点也就是反转后的prev链表长度小于 k 时崩溃没有检查快指针是否会走到 NULL快指针走 k 步时逐次判断是否为空这个表里的每一项我都至少在本地调试时见过一次。尤其是最后一项链表长度小于 k 的情况很多人只在 for 循环里走 k 次但没有检查中途 fast 是不是已经变成 NULL结果在 while (fast) 里才会暴露问题。6.2 指针顺序的黄金原则链表OJ里的错误大概有七成是“顺序错”。我把自己的经验总结成一条规则任何要修改某个节点 next 的语句都必须保证你需要的后继指针在修改之前已经拿到了。这句话适用反转链表、尾插、头插、分割链表、删除节点等几乎所有场景。写代码的时候先在草稿纸上把“指针断掉之前谁还被引用”标出来就不会出现改完才发现没保存的情况。6.3 本地测试环境怎么搭很多同学只依赖 OJ 的判题反馈提交一次错了再提交一次再猜效率很低。我更建议把本地调试环境搭起来自己构造输入自己看输出。一个最小化的辅助代码大概长这样struct ListNode* createNode(int val) { struct ListNode* node (struct ListNode*)malloc(sizeof(struct ListNode)); node-val val; node-next NULL; return node; } struct ListNode* createList(int arr[], int n) { struct ListNode dummy; dummy.next NULL; struct ListNode* tail dummy; for (int i 0; i n; i) { tail-next createNode(arr[i]); tail tail-next; } return dummy.next; } void printList(struct ListNode* head) { struct ListNode* cur head; while (cur) { printf(%d - , cur-val); cur cur-next; } printf(NULL\n); }有了这三个函数你可以在 main 里手动构造空链表、单节点链表、环形链表、相交链表再调用要测试的函数把结果打印出来。链表题最怕的就是“在脑子里跑程序”但人脑跑程序非常容易漏掉状态变化。本地跑一遍结果一目了然。6.4 调试链表题的三个土办法我调试链表题基本不靠断点而是用三个土办法。第一是打印在关键循环前后打印当前节点的 val以及接下来一步指向哪里。第二是计步如果怀疑死循环可以在循环里加一个计数器超过节点总数的合理倍数就强制退出再检查是不是指针绕圈了。第三是画图每轮循环都画一次当前链表的状态节点值标在方框里next 用箭头表示画完通常自己就能找到问题。链表OJ和数组题最不一样的地方就是写代码之前必须能“看见”每个指针的移动轨迹。我刷了很多题之后最大的体会是你不一定需要做多少难题但要把每道做过的题的边界情况全想透。自己做一遍、在本地搭一个测试环境、把错误分类记录下来这套流程走下来之后再看到新题就会顺手很多。
很多人学数据结构前面的顺序表、单链表增删查改都写得顺一到“链表OJ”就开始怀疑自己。我见过不少同学课能听懂、增删接口也能写但面对在线判题平台上一道一道链表题就卡住要么空指针崩溃要么提交十几次都过不了要么代码看着没问题运行结果却总是差一个节点。链表OJ其实不是考“谁记得接口多”它考的是你能不能把链表的指针关系看明白把边界情况想全把思路画成图再落成代码。这篇笔记适合刚学完链表基础知识、准备开始刷题的人也适合之前刷得磕磕绊绊、想系统整理一遍的人。我会把链表OJ最常见的题型、解法思路、推导过程和踩坑经验一起整理出来当作一版随时能回来翻的笔记。1. 链表OJ到底在练什么先别动手想清楚这三件事很多人一看到链表OJ题第一反应是打开编译器直接写。真正高效的顺序其实是先画图再想边界最后才写代码。链表题目有一个共同点——代码量不大但只要你少考虑一个条件结果就是段错误或者死循环。它的难度几乎全部集中在“看不见”的地方所以动手之前先在脑子里把运行过程过一遍比盲目提交试错重要得多。1.1 画图能力决定你能不能动手链表跟数组最大的区别是数组的下标是连续的你知道当前下标就能直接访问下一个链表则完全依靠 next 指针每个节点都不知道自己的后继是谁除非你拿着头指针从头遍历。所以链表题的几乎所有操作归根结底都是“改变指针指向”而不是“移动下标”。做题时不画图等于蒙着眼睛开车。最典型的例子就是单链表反转。你打算让当前节点的 next 指向前一个节点问题是这一指当前节点原本的后继节点就找不到了。如果不先把 next 保存下来链表当场断成两截。这个“先保存后继再改指向”的思路画一遍立刻明白闭眼写就容易崩。我给初学者的建议是每道链表OJ题先在草稿纸上画三个节点模拟两三轮指针移动把每一轮每个指针分别指向哪里写清楚再动手写代码。这样看起来慢实际比自己反复调试要快得多。1.2 边界条件意识空链表、单节点、尾节点链表OJ最容易挂的不是算法而是边界。空链表、只有一个节点、只有两个节点、删除最后一个节点、找倒数第一个节点、链表有环、链表相交……每一种情况稍不注意就是空指针解引用或者直接死循环。数组题里你可能只需要关心 i n链表题里你至少要关心三件事当前节点是否为空、当前节点的 next 是否为空、指针移动之后会不会跳出链表。我自己整理笔记时有个习惯拿到一道题先把题目给的条件列表里的边界情况列在旁边。比如题目说“链表可能为空”那空链表的情况必须在所有测试里排第一个。然后想单节点和双节点的情况等这些在本地都能跑过再上 OJ 提交。边界条件如果都要靠判题系统反馈才知道刷题效率会非常低但如果你在本地主动构造这些输入反而能积累出很强的边界直觉。1.3 指针模型切断和重接链表OJ还会逼你建立一种“指针模型”head 是第一个节点的地址p-next 是下一个节点的地址修改 p-next 不会改变节点里的 val。如果你想让一个节点从 A 链表挪到 B 链表只需要让 B 的尾节点指向它再让 A 的前一个节点指向它的 next本质上就两个动作切断旧链接、重接新链接。带着这个模型去看题目会发现反转链表、分割链表、合并有序链表都是同一套动作的变体。你只需要关心两件事当前节点是谁它的 next 在改变之前还存在不存在。很多同学写链表题容易乱就是因为把注意力放在“结果长什么样”上而不是“每一步指针怎么跳”上。后面每个题型本质上都在反复训练这个模型。2. 反转链表迭代和递归两条路但同一个核心反转链表几乎是链表OJ里必考的第一道题。它看起来特别简单但迭代和递归两种写法都藏了不少细节。这道题如果能在不看答案的情况下独立写对说明你的链表指针基础基本过关了。2.1 迭代版本三指针穿针引线迭代反转的核心语句是每次把当前节点 cur 的 next 指向前一个节点 prev然后整体右移。但注意cur-next 一旦被修改原来 cur 后面的节点就找不到了所以必须在修改之前先把原后继保存下来。代码是这样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; // 移动 prev cur next; // 移动 cur } return prev; }你可以在草稿纸上画一个三段链表让 prev 一开始指向 NULLcur 指向头节点。第一轮把头节点 next 改成 NULL头节点就被“摘”下来了同时 prev 走到头节点位置cur 走到原第二个节点。第二轮第二个节点的 next 改成指向头节点链表第一段开始倒过来。如此循环到 cur 为 NULL 时prev 正好停在整个链表的最后一个节点上也就是反转后的新头。很多同学写错的地方有两个一是不先保存 next结果修改完 cur-next 之后循环里根本找不到后续节点二是循环结束返回 cur但 cur 此时是 NULL正确返回值应该是 prev。要记住反转链表的头节点永远是原链表的尾节点。2.2 递归版本从后往前改 next递归的代码更短但抽象程度更高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它后面的链表已经全部反转好了newHead 指向反转后的新头也就是原链表的尾节点。而 head 原本的后继节点 head-next现在正好是反转后链表的最后一个节点。所以需要让 head-next-next head把当前节点接回到反转链表的尾部再把 head-next 置空防止形成环。递归写法的常见错误是漏掉 head-next NULL。如果不置空最后一个节点可能还会指向原链表中的某个节点造成结果带环或者输出超长。递归反转虽然看起来优雅但初学阶段如果觉得难可以先只用迭代版本等理解了栈帧和回溯之后再来补递归。2.3 为什么看懂了答案自己写还是崩我见过很多同学看书看题解都懂一到自己写就卡住。原因通常是只记住了“步骤”没有真正验证指针顺序。反转链表最怕的就是在循环里“先改 next再保存 next”这个顺序错一步整段链表就断了。我的建议是把迭代版本循环内的四行代码按顺序背下来每行在做什么写在注释里然后自己画图推一遍。不要只看题解的最终代码要在草稿纸上把每轮循环的 prev、cur、next 三个指针的位置全部标出来。等你亲手画完三轮这类题基本上就不会再错了。3. 快慢指针全家桶从找中点到环入口链表OJ里有一个特别大的套路家族叫快慢指针。它用两个指针一个每次走一步另一个每次走两步通过速度差来达到“探测结构”的目的。找中间节点、找倒数第 k 个节点、判断链表是否有环、找环入口全都能用这一套思路解决。这个套路一旦掌握很多中等题就能直接降维。3.1 找中间节点快慢指针最基础的应用找链表中间节点的代码非常短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; }这里的逻辑是fast 的速度是 slow 的两倍当 fast 走到链表末尾时slow 正好在链表中间。问题是链表长度分奇偶两种情况链表有奇数个节点时fast 最后一次停在最后一个节点slow 会停在正中间链表有偶数个节点时fast 最终会走到 NULLslow 停在第二个中间节点上。很多题目需要的是“后半段的头节点”比如回文链表这时取第二个中间节点正好合适。如果你需要取偶数情况的第一个中间节点可以加一个虚拟头节点或者把循环条件改成 fast-next 和 fast-next-next但初阶阶段默认取第二个中间节点是最常见的直接用上面的代码就可以了。找倒数第 k 个节点也是同一个套路让快指针先走 k 步然后快慢指针一起每次走一步。快指针走到 NULL 时慢指针正好指向倒数第 k 个节点。但这里要额外处理链表长度小于 k 的情况struct ListNode* getKthFromEnd(struct ListNode* head, int k) { struct ListNode* fast head; struct ListNode* slow head; for (int i 0; i k; i) { if (fast NULL) { return NULL; // 链表长度小于 k } fast fast-next; } while (fast) { slow slow-next; fast fast-next; } return slow; }先走的 k 步本质上是在制造“偏移量”让两个指针之间始终保持着 k 个节点的距离。这样快指针到达 NULL 时慢指针距离末尾也是 k 步自然就是倒数第 k 个节点。3.2 判断是否有环跑得快的总会被跑得慢的追上环形链表的判断是快慢指针的高频应用之一。代码几乎和找中点一样只是多了一个相等判断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; }你可以想象两个人在环形跑道上跑步快的人速度是慢的人的两倍。只要跑道存在闭环快的人最终一定会从后面追上慢的人如果跑道没有闭环快的人会先到达终点 NULL循环直接结束。这个写法里有几个容易踩的坑循环条件必须同时判断 fast 和 fast-next因为 fast 每次走两步少了任何一个判断空链表或单节点链表都可能直接解引用空指针。另一个坑是相等判断必须放在移动之后不能在循环开头判断否则 slow 和 fast 初始都指向 head会被误判成有环。3.3 找环入口一个需要数学推导的经典问题判断有环之后题目通常会更进一步返回环的入口节点。这个问题的推导值得认真看一遍。假设头节点到环入口的距离是 a环入口到两个指针第一次相遇点的距离是 b相遇点继续走到环入口的距离是 c那么环的周长 L 就是 b c。slow 进环后走的路程是 a bfast 走的路程是 a b nL其中 n 表示 fast 在追上 slow 之前已经在环里多走了 n 圈。因为 fast 的速度是 slow 的两倍所以 fast 总路程等于 slow 总路程的两倍于是a b nL 2 * (a b) a b nL a nL - b a (n - 1)L c这个结果的含义是如果从链表头节点出发走距离 a同时从相遇点出发走距离 c也就是沿着环继续走到入口的距离两个指针会在环入口恰好相遇。因为 a 可以被拆成“n-1 圈完整的环”再加一段 c最终它们会落在同一个点上。所以代码的写法是先用快慢指针找到相遇点一旦相遇把一个指针拉回 head另一个留在相遇点两个指针都改成每次走一步再走一定步数后的相遇位置就是环入口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) { struct ListNode* p head; struct ListNode* q slow; while (p ! q) { p p-next; q q-next; } return p; } } return NULL; }3.4 快慢指针的常见翻车点快慢指针整体思路不难但细节很多我自己刷题时整理过几个高频翻车点。第一个是循环条件写成 while (fast-next)没有检查 fast 本身是否为空空链表直接崩。第二个是判环时先判断相等再移动导致初始状态就被误判为有环。第三个是有人为了加快速度把 fast 改成每次走三步甚至四步结果相对速度不再是 1反而可能跳过相遇点或者写出错乱结果。快慢指针最稳妥的设定永远是 slow 走一步、fast 走两步不要为了炫技乱改步长。4. 合并有序链表、相交链表、分割链表链表的“拼接艺术”如果反转链表练的是“指针方向”那合并、相交、分割这三类题练的就是“链表拼接”。它们都不是很难但特别容易在细节上出问题尤其是头节点不确定的情况怎么处理。4.1 合并两个有序链表哨兵节点解决头为空的问题合并两个有序链表的思路和合并两个有序数组很像两个链头同时开始谁的值小就取谁。但链表有一个麻烦新链表的头节点可能是 l1 的头节点也可能是 l2 的头节点写起来得提前判断。一个更简单的办法是用哨兵节点也叫 dummy 节点struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) { struct ListNode dummy; dummy.next NULL; struct ListNode* tail dummy; while (l1 l2) { if (l1-val l2-val) { tail-next l1; l1 l1-next; } else { tail-next l2; l2 l2-next; } tail tail-next; } tail-next l1 ? l1 : l2; return dummy.next; }哨兵节点最大的作用是让所有新节点插入的逻辑保持一致不需要在循环里判断“当前新链表是不是空的”。最后l1 和 l2 中一定有一个已经走到 NULL另一个剩余部分本身就是有序的直接让 tail-next 接上剩余链表即可。需要提醒的是这里没有 malloc 一个新的哨兵节点而是在栈上定义了一个局部变量 dummy。这样做不需要手动释放返回 dummy.next 也安全。如果你改用 malloc 创建哨兵节点记得在函数结束前 free 掉否则会有内存泄漏。4.2 相交链表用“走完对方的路”来消除长度差相交链表的意思是两个链表从某个节点开始后面的节点完全共享。求第一个相交节点最简单的做法是先算出两个链表各自的长度然后让长链表先走长度差再两个指针一起走第一个相等的节点就是交点。还有一种更巧妙的写法不需要先求长度而是让两个指针循环交替遍历两个链表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; }你可以想象两个指针分别从两个链表出发当某一个指针走到 NULL 时立刻跳到另一个链表的头节点继续走。这样做的效果是pA 和 pB 都走过了“A链表长度 B链表长度”的总路径长度差异被彻底抹平。如果两个链表相交它们会在某个节点碰上如果完全不相交它们最终会同时走到 NULL循环结束返回 NULL。这个解法的代码很短但它背后“用路径来抵消长度差”的思想值得多画几遍图。尤其是两个链表长度差特别大的情况纸上推一遍才能理解为什么两个指针最后能同步。4.3 分割链表拆成两个链表再拼回去分割链表一般长这样给定一个链表和一个值 x要求把所有小于 x 的节点放在所有大于等于 x 的节点前面并且保持原有的相对顺序。这个题不能简单排序因为题目要求每个区间的相对顺序不变。我的做法是维护两个哨兵链表一个装小于 x 的节点一个装大于等于 x 的节点。遍历原链表按值把每个节点尾插到对应的链表中最后把两个链表接起来struct ListNode* partition(struct ListNode* head, int x) { struct ListNode lessHead; struct ListNode greaterHead; lessHead.next NULL; greaterHead.next NULL; struct ListNode* ltail lessHead; struct ListNode* gtail greaterHead; struct ListNode* cur head; while (cur) { struct ListNode* next cur-next; // 先保存后继 if (cur-val x) { ltail-next cur; ltail cur; } else { gtail-next cur; gtail cur; } cur next; } gtail-next NULL; // 让大值链表正确收尾 ltail-next greaterHead.next; return lessHead.next; }这里有两个关键点。第一每次移动 cur 时必须先把 cur-next 保存下来因为你会把 cur 接到新链表上原链表的关系已经不存在了。第二最后必须让 gtail-next NULL否则尾节点可能还指向原链表后面的某个节点导致新链表成环或输出多了内容。这类“拆开再拼接”的题只要画出两个哨兵链表的接入过程其实比想象中简单。很多同学容易写错的地方恰恰是忘记在原链表里保存 next。5. 回文链表与排序链表组合题是真正的分水岭单点技巧刷熟之后就要开始接触组合题。组合题不会特别难但要求你把前面几类题型的技能串起来比如找中点、反转链表、合并链表。这类题很容易出现在课后练习里也很适合检验自己是不是真理解了每个基础操作。5.1 回文链表找中点 反转后半段 双指针比较回文链表要求判断一个链表是否前后对称比如 1 - 2 - 3 - 2 - 1 就是回文。数组的回文判断很简单从两边往中间比较即可但链表不能从后往前遍历所以常用技巧是先用快慢指针找到链表中点再把后半段链表反转最后从前半段头节点和反转后的后半段头节点同时开始比较。bool isPalindrome(struct ListNode* head) { if (head NULL || head-next NULL) { 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; }这段代码里slow 指向链表中间节点。如果是奇数长度的链表slow 正好在正中间反转后半段之后多比较一次中间节点也无妨如果是偶数长度的链表slow 指向第二个中间节点反转后半段之后正好能完成长度相等的两段比较。这个方法会破坏原链表结构不过大多数 OJ 题只关心返回值所以问题不大。如果面试要求不破坏原链表可以在比较完后再把后半段反转回去。5.2 排序链表用前面所有技巧做一次综合检验排序链表是个更进阶的组合题。它要求把链表排成升序常见解法是归并排序先找中点把链表拆成前后两半递归排序然后用归并两个有序链表的逻辑合并。这个过程会把快慢指针找中点和合并两个有序链表两个技巧同时用上是不错的综合训练。递归版的排序链表代码不长思想也清楚但因为每层递归都要重新用快慢指针找中点总复杂度仍然稳定在 O(n log n)。如果题目要求严格的 O(1) 额外空间那就得改成自底向上的迭代归并代码会复杂不少。初阶阶段不用一开始就死磕迭代版本先把递归版本理解透知道它用到哪些前面学过的技能就已经达到综合检验的目的了。6. 我的避坑清单链表OJ里那些“必挂”的写法这部分是我自己刷题和帮别人看代码时最常遇到的错误把它们整理成一张表方便复习的时候直接对照。6.1 最常犯的错误类型错误现象可能原因正确做法空链表直接崩溃循环里没有判断当前指针是否为空while 条件写成p p-next反转链表后丢了一半节点修改cur-next前没有保存后继先保存next再改指向判环对单节点链表误判相等判断写在了指针移动之前先移动再判断是否相等合并或分割后链表成环尾节点的 next 没有置 NULL拼接完成后主动tail-next NULL返回值总是 NULL反转后返回了cur而不是prev返回原链表的尾节点也就是反转后的prev链表长度小于 k 时崩溃没有检查快指针是否会走到 NULL快指针走 k 步时逐次判断是否为空这个表里的每一项我都至少在本地调试时见过一次。尤其是最后一项链表长度小于 k 的情况很多人只在 for 循环里走 k 次但没有检查中途 fast 是不是已经变成 NULL结果在 while (fast) 里才会暴露问题。6.2 指针顺序的黄金原则链表OJ里的错误大概有七成是“顺序错”。我把自己的经验总结成一条规则任何要修改某个节点 next 的语句都必须保证你需要的后继指针在修改之前已经拿到了。这句话适用反转链表、尾插、头插、分割链表、删除节点等几乎所有场景。写代码的时候先在草稿纸上把“指针断掉之前谁还被引用”标出来就不会出现改完才发现没保存的情况。6.3 本地测试环境怎么搭很多同学只依赖 OJ 的判题反馈提交一次错了再提交一次再猜效率很低。我更建议把本地调试环境搭起来自己构造输入自己看输出。一个最小化的辅助代码大概长这样struct ListNode* createNode(int val) { struct ListNode* node (struct ListNode*)malloc(sizeof(struct ListNode)); node-val val; node-next NULL; return node; } struct ListNode* createList(int arr[], int n) { struct ListNode dummy; dummy.next NULL; struct ListNode* tail dummy; for (int i 0; i n; i) { tail-next createNode(arr[i]); tail tail-next; } return dummy.next; } void printList(struct ListNode* head) { struct ListNode* cur head; while (cur) { printf(%d - , cur-val); cur cur-next; } printf(NULL\n); }有了这三个函数你可以在 main 里手动构造空链表、单节点链表、环形链表、相交链表再调用要测试的函数把结果打印出来。链表题最怕的就是“在脑子里跑程序”但人脑跑程序非常容易漏掉状态变化。本地跑一遍结果一目了然。6.4 调试链表题的三个土办法我调试链表题基本不靠断点而是用三个土办法。第一是打印在关键循环前后打印当前节点的 val以及接下来一步指向哪里。第二是计步如果怀疑死循环可以在循环里加一个计数器超过节点总数的合理倍数就强制退出再检查是不是指针绕圈了。第三是画图每轮循环都画一次当前链表的状态节点值标在方框里next 用箭头表示画完通常自己就能找到问题。链表OJ和数组题最不一样的地方就是写代码之前必须能“看见”每个指针的移动轨迹。我刷了很多题之后最大的体会是你不一定需要做多少难题但要把每道做过的题的边界情况全想透。自己做一遍、在本地搭一个测试环境、把错误分类记录下来这套流程走下来之后再看到新题就会顺手很多。
：残差+注意力+软阈值化的抗噪分类实战)
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
