链表进阶实战：反转、快慢指针与环形检测全解析-北京尧图网络

昨天还在写链表的创建、遍历、插入、删除觉得链表也就那么回事今天刚开始练反转和判环就被指针绕得有点晕。如果你也有同感这篇笔记应该能帮上忙。第二天的主角是链表的进阶操作单链表反转、快慢指针找中点、环形检测、删除倒数第N个结点、合并有序链表、判断相交最后还要用这些操作组合起来解决回文判断。适合刚学完链表基础增删改查、准备进入刷题或面试阶段的读者。文章里的代码我用 C 写核心是讲清楚每一次指针移动换成 C 或 Python 思路完全一样。1. 链表进阶到底在“进”什么先建立操作坐标系1.1 为什么第二天就上“进阶”很多人学链表会卡在第一个反差上基础操作都是顺着 next 走逻辑非常直白进阶操作却要让多个指针互相配合甚至还要在递归里改指向。第二天练这些不是因为基础不重要而是因为链表的真正难点从来不是语法而是“在内存里只能靠指针定位节点”这个抽象。你没法通过下标随机访问第 k 个节点也没有现成的 length 函数很多操作都必须从头遍历。进阶套路的价值就是在这种限制下仍然做到 O(n) 时间、O(1) 额外空间。还有一个更实际的原因这些操作在工程里确实经常出现。像缓存淘汰、任务调度、编辑器撤销历史、链式哈希的冲突处理底层多多少少都会涉及链表的反转、合并或环形检测。练一天基础第二天上这些时间线本身不算激进。把反转和快慢指针玩熟后面学树、图、跳表的时候你会发现自己对指针的掌控力完全不一样很多看似新的结构也能很快迁移过去。1.2 基础结点定义与几个辅助函数为了避免每个例子都重复写环境代码先把这一系列内容里会用到的基础结构定下来。下面这几段代码不复杂但后面所有操作都会复用它们。单独把它们拎出来是为了让反转、判环、合并这些函数看起来更干净也方便你自己调试时直接复制。#include stdio.h #include stdlib.h typedef struct Node { int val; struct Node *next; } Node; Node *createNode(int val) { Node *p (Node *)malloc(sizeof(Node)); p-val val; p-next NULL; return p; } void printList(Node *head) { while (head) { printf(%d - , head-val); head head-next; } printf(NULL\n); } void freeList(Node *head) { Node *tmp; while (head) { tmp head-next; free(head); head tmp; } }printList 和 freeList 在两个地方特别好用一是手动构造测试用例后快速确认链表形状二是写完操作函数后立刻打印结果看节点顺序是否符合预期。这里不做复杂封装是因为学习阶段把每一步摊开反而更容易理解。等这些操作都熟练了再考虑封装成链表库也不迟。1.3 复杂度思维指针操作的本质是“定位”不是“搬运”链表进阶操作有个共同规律节点本身不搬搬的全是指针。反转没有创建新节点判环没有复制链表删除倒数第N个也只改了一两个 next。由于每次定位一个节点都要从 head 开始走所以绝大多数操作至少是 O(n)只要能想清楚指针之间的关系额外空间可以压到 O(1)。这也是面试里反复追问复杂度的地方不是要你背 O(n)而是看你能不能区分哪些遍历是必须的哪些能通过双指针省掉。下面这张表把第二天会碰到的操作按套路归了一下类。你会发现很多题目根本不用死记代码本质上就是快慢指针、反转、dummy node 这几个套路的组合。操作核心套路时间复杂度额外空间单链表反转三指针迭代 / 递归O(n)O(1) 或 O(n) 递归栈找中间结点快慢指针O(n)O(1)环形检测快慢指针相遇O(n)O(1)删除倒数第N个双指针 dummy nodeO(n)O(1)合并有序链表dummy node 尾插O(mn)O(1)判断相交长度对齐同步走O(mn)O(1)2. 单链表反转从“三指针”到递归核心是别让后半段链表丢2.1 迭代反转三指针一次遍历反转是链表进阶头号操作。思路说破也不复杂从头开始遍历把每个节点的 next 改成前一个节点。问题在于你一旦改了 cur-next原来 cur 后面的节点就找不到了所以必须用一个临时指针先把下一个节点保存下来。这就是迭代反转里三个指针存在的意义prev 指向前一个节点cur 指向当前要改的节点next 保存 cur 原本的下一个节点。Node *reverseIter(Node *head) { Node *prev NULL; Node *cur head; Node *next NULL; while (cur ! NULL) { next cur-next; // 先保存下一个节点 cur-next prev; // 当前节点指向前一个 prev cur; // prev 后移 cur next; // cur 后移 } return prev; // 原链表最后一个节点变成新头 }以 1-2-3-NULL 为例第一轮先把 2 存到 next然后让 1-NULLprev 变成 1cur 变成 2第二轮让 2-1第三轮让 3-2。最后 cur 到 NULLprev 停在节点 3 上返回 prev 就是反转后的新头。整个过程没有新建节点没有复制数据只是把每个节点的 next 掉了个头。2.2 递归反转让函数自己“翻”递归版本的核心是先走到链表最后再一层层往回改 next。很多人觉得递归难是因为它把“先改指针”变成了“先到底再回溯时改”。看代码时不要试图跟踪每一层只需要相信reverseRecur(head-next) 返回的是从下一个节点开始的、已经反转好的子链表。Node *reverseRecur(Node *head) { if (head NULL || head-next NULL) { return head; } Node *newHead reverseRecur(head-next); head-next-next head; // 让下一个节点反过来指向自己 head-next NULL; // 自己原来的 next 置空 return newHead; }递归版本写起来很简洁但代价是递归栈的深度等于链表长度。链表太长时容易栈溢出所以工程代码里更常写迭代版本递归版本更多用来考察对递归过程的理解。无论哪种写法都要注意把 head-next 置空否则反转后的链表尾部可能还残留一条指向旧位置的线调试时就会遇到莫名其妙的环。2.3 反转操作的边界条件与典型应用反转最容易被忽略的是边界。空链表直接返回 NULL只有一个节点时迭代循环不进入递归入口也直接返回 head。这两个边界恰好都被条件 cur ! NULL 或 head-next NULL 挡在了前面所以写代码时不需要额外特判。反转在实战里极少单独考更多是作为子步骤出现。比如按 K 个一组反转链表比如回文判断再比如反转后半段来比较。把这些题目拆开看你会发现核心都是“先整体会反转再想清楚从哪个节点开始反转”。所以第二天的练习里反转不只是背代码而要真正能手写出来并且说得清楚每一步在干什么。3. 双指针家族找中点、判环、倒数第N个结点一次讲清3.1 快慢指针找中间结点几乎所有双指针技巧都是从找中间结点入门的。结论很直白快指针每次走两步慢指针每次走一步当快指针到链表尾部时慢指针恰好在中间。代码只有几行但有两个细节值得单独说。Node *findMiddle(Node *head) { if (head NULL) { return NULL; } Node *slow head; Node *fast head; while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; } return slow; }第一个细节如果链表长度是奇数返回正中间结点如果是偶数返回第二个中间结点。比如 1-2-3-4返回 3 而不是 2。很多回文、对折类题目默认要第二个中间结点所以这个版本用起来最顺手。第二个细节while 条件必须判断 fast ! NULL 和 fast-next ! NULL因为 fast 一次跳两步如果不检查 fast-next下一步就可能访问空指针。3.2 Floyd 判圈算法为什么快慢指针一定会相遇判环本质上是找中点的一个变种同样用快慢指针但这次不关心终点只关心两者是否相遇。如果链表中没有环fast 会先碰到 NULL函数正常返回 false如果有环fast 会在环里一直转slow 进入环后两者之间的距离每次循环减少 1最终必然相遇。这里的核心不是“快指针跑得比慢指针快”而是相对速度是每轮 1 个节点所以追及问题一定有解。bool hasCycle(Node *head) { if (head NULL || head-next NULL) { return false; } Node *slow head; Node *fast head; while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; if (slow fast) { return true; } } return false; }写这段代码时最常犯的错误是 while 里只判断 fast ! NULL。如果链表恰好没有环循环最后 fast 会停在 NULL下一轮再执行 fast-next-next 就直接崩溃。如果面试官进一步问环的入口Floyd 算法还有第二阶段相遇之后把 slow 重置到 head然后两个指针都一次走一步再次相遇的位置就是环入口。这个概念可以先记下来作为后面拓展练习。3.3 删除倒数第N个结点一次遍历的偏移量技巧删除倒数第 N 个结点不用反转也不用先遍历一遍求长度再走第二遍。办法是让两个指针拉开 N 个节点的距离然后同步向后走快指针先走 N 步当快指针走到链尾时慢指针的 next 正好指向要删除的节点。这里用 dummy 哨兵结点还有一个额外好处删除头结点时不需要单独特判。Node *removeNthFromEnd(Node *head, int n) { Node dummy; dummy.val 0; dummy.next head; Node *fast dummy; Node *slow dummy; while (n 0 fast ! NULL) { fast fast-next; n--; } while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next; } Node *toDelete slow-next; slow-next slow-next-next; free(toDelete); return dummy.next; }为什么需要 dummy因为 slow 要从 head 的前一个位置开始走。如果链表只有一个节点且 n1没有 dummy 的话你会陷入“要删头结点但找不到它的前驱”的尴尬局面。有了 dummyslow 指向 dummyfast 先走一步到唯一节点然后循环不进入slow-next 正好就是要删除的头结点。处理完之后返回 dummy.next新链表头就自动更新了。4. 有序链表合并、相交检测、回文判断组合拳怎么打4.1 合并两条有序链表dummy node 的妙处合并两个有序链表是一道很经典的题迭代版本的核心是 dummy node 加尾插法。每次从 l1 或 l2 里挑一个值更小的节点接到 tail-next 上然后移动对应链表的指针和 tail。整个过程没有创建新节点只是把已有节点重新串起来。Node *mergeTwoLists(Node *l1, Node *l2) { Node dummy; dummy.next NULL; Node *tail dummy; while (l1 ! NULL l2 ! NULL) { if (l1-val l2-val) { tail-next l1; l1 l1-next; } else { tail-next l2; l2 l2-next; } tail tail-next; } tail-next (l1 ! NULL) ? l1 : l2; return dummy.next; }这里有个很重要的提醒dummy 是栈上的局部变量返回 dummy.next 完全没问题但绝不能返回 dummy因为函数返回后栈空间就失效了。另外当一个链表遍历完另一个链表可能还有剩余节点直接 tail-next l1 ? l1 : l2 就能把剩余部分整体接上不需要继续 while 循环。这个技巧在合并链表的同类题目里经常复用。4.2 相交链表先对齐长度再双指针同步走判断两个链表是否相交最自然的办法是求长度然后对齐。为什么不能直接从两条链表的头部一起走因为两条链表在相交之前长度可能不一样相交之后的部分虽然长度一致但起点错位两个指针根本对不上。所以先让长链表走掉长度差然后再同步比较。int listLength(Node *head) { int len 0; while (head ! NULL) { len; head head-next; } return len; } Node *getIntersectionNode(Node *headA, Node *headB) { int lenA listLength(headA); int lenB listLength(headB); Node *pa headA; Node *pb headB; while (lenA lenB) { pa pa-next; lenA--; } while (lenB lenA) { pb pb-next; lenB--; } while (pa ! NULL pa ! pb) { pa pa-next; pb pb-next; } return pa; }如果两条链表确实相交pa 和 pb 最终会在同一个节点相遇如果没有相交它们会一起走到 NULL最终返回 NULL。这个方法的时间复杂度是 O(mn)额外空间 O(1)。另有一种不额外求长度的双指针交替遍历法思路更巧妙但理解成本更高建议先把长度对齐这个版本写熟。4.3 回文判断快慢指针反转的组合题回文判断非常适合放在“第二天”的末尾因为它把前面很多操作串起来了。思路是先用快慢指针找到后半段起点再反转后半段最后从原链表头和反转后的头同步比较。代码量不大但每一行都在调用之前的“基本功”。bool isPalindrome(Node *head) { if (head NULL || head-next NULL) { return true; } Node *slow head; Node *fast head; while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; } Node *rev reverseIter(slow); while (rev ! NULL) { if (head-val ! rev-val) { return false; } head head-next; rev rev-next; } return true; }这个实现会修改原链表所以在面试或竞赛里要确认是否允许修改输入。如果要求不改变原链表一种常见做法是借助栈保存前半段节点再与后半段比较或者复制一份链表再反转不过额外空间会变成 O(n)。从进阶角度讲能想到把“找中点”和“反转”组合起来比单独背一个回文判断代码更有价值。5. 链表进阶操作的坑与调试实录从崩溃到死循环5.1 空指针解引用十个链表 bug 九个在这链表题最经典的崩溃是把空指针的 next 拿来赋值。常见场景包括while 循环里没判 fast fast-next 就访问 fast-next-next删除节点时先写 slow-next slow-next-next但没确认 slow-next 不是 NULL递归反转时没有处理空链表入口。我的调试习惯是每写一个 while先问自己一句这个循环最后停在哪里如果停在 NULL 上那循环体里能安全访问的指针有哪些把这个问题想清楚大部分空指针问题可以在代码写出来之前就消灭掉。5.2 反转里的顺序错误和递归尾部残留反转三指针的代码很容易把顺序写错。假如你先写 cur-next prev再写 next cur-next那 next 拿到的已经不是原来的下一个节点了后半截链表直接丢失。正确的顺序永远是先用 next 保存 cur-next再修改 cur-next最后整体移动。这个顺序不是代码风格问题是正确性问题。递归反转也有一个常见错误改完 head-next-next head 之后忘记把 head-next 置为 NULL。这会让链表的最后一个节点仍然指向它的前一个节点打印或遍历时可能出现死循环。排查这类问题时建议直接把链表打印出来如果看到 1 - 2 - 3 - 2 - 3 这种重复序列基本就是尾部没有断环。5.3 边界测试法1 个结点、2 个结点、空链表链表进阶操作靠“看起来对”是不够的边界测试必须做深。我建议每个操作都至少跑下面四个用例测试用例需要重点检查的点空链表函数入口是否处理 NULL1 个节点反转/删除/回文等操作是否正确保留节点2 个节点指针交换、删除头或尾是否正确偶数长度链表快慢指针返回哪个中间节点比如反转 1-2正确结果是 2-1如果结果还是 1-2大概率是指针移动顺序写错。删除倒数第 1 个节点时用 1-2-3 测试正确结果是 1-2。这类小用例看起来简单但能把大部分逻辑错误挡在提交之前。测试时可以配合 createNode 手动构造链表再用 printList 在每个关键步骤后打印观察形状变化。5.4 写链表代码的几个个人习惯最后分享几个我自己写链表代码时的习惯。第一先画再写尤其是反转、相交这种跨步操作在纸上画一张图往往比盯着屏幕半天下结论要快得多。第二用最短的链表验证核心逻辑比如 1-2-3-4每执行一步就用 printList 看结果。第三写删除相关函数时先决定哪些节点会被回收记得调用 free避免多次运行后出现内存泄漏。第四如果函数会修改输入链表在注释里明确写出来避免调用者以为原链表还能继续使用。我第二天练下来最大的感受是链表进阶操作没有一个需要死记硬背。反转就是把 next 先保存下来再改快慢指针就是用相对速度解决定位问题dummy node 是为了把边界情况变成普通情况。真正难的不是代码是动手前有没有把指针关系画明白。只要这个习惯养成了后面再遇到更复杂的数据结构你会比别人稳很多。

链表进阶实战：反转、快慢指针与环形检测全解析

相关推荐

企业微信AI智能客服系统设计与实战：从回调接入到多轮对话落地

YOLOv5-ready橙子成熟度数据集：开箱即用的农业视觉交付包

AIS数据解析全流程：从串口驱动到船舶轨迹可视化

更多资讯

STM32 CAN总线实战：从协议原理到配置收发

多模态Agent如何规划UI测试路径：从感知融合到动态决策的工程实践

多步任务总在细节崩盘？用技能编排让智能体真正稳定

Agent技能系统实战：为大模型装上可插拔的“手”和“脚”

AnyPS5：跨平台文件处理与格式转换的轻量化解决方案

UCINET数据导入实战：格式规范、Excel整理与高频排错

今日更新

声子晶体仿真：三角晶格与六角晶格的能带计算实战

度假村安保定岗定编：岗位梳理、编制测算与排班设计

COMSOL等离子体模块实战：氩气双层DBD仿真建模全解析

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？