上周三晚上十一点多一个刚转方向学 C 的朋友给我发消息说 Reverse Linked List 这道题他看了三遍题解合上编辑器还是写不对指针一改就断链。这事儿我太熟了——链表反转是算法题里少见的「代码不到十行、坑却有一箩筐」的典型难度标记 Easy但真正能一次性写对、并且讲清楚每一行指针为什么这么动的人比例并不高。这篇记录来自我自己刷 C 算法题时留下的笔记围绕 Reverse Linked List反转链表这道 Easy 题展开。我会把迭代、递归、头插法三种写法逐行拆开把本地自测环境的搭建、编译命令、常见报错的排查过程都写进去再顺手把它延伸出去的区间反转、K 个一组反转一起串一遍。它不是给判题机交作业用的答案而是一份能落地复现的工程笔记你在 VSCode 里新建一个 .cpp 文件照着敲一遍就能在本机跑出结果、看到每一轮指针的变化。适合谁看如果你刚学完 C 的结构体和指针还没真正搞明白「指针的指针在什么位置被改写」这篇能帮你把地基夯一遍如果你已经能默写迭代版但一到递归版本就卡壳或者面试被追问「能不能 O(1) 空间」「K 个一组怎么处理」第三、第四节的细节和排查表会让你少走很多弯路。链表这块东西没有花哨的数学考的就是对指针、边界、内存这三个东西的掌控力而这三样恰好是 C 的基本功。1. 整体设计与思路拆解先想清楚要动什么1.1 反转链表到底在解决什么问题把问题翻译成人话给你一条单向链表比如 1 - 2 - 3 - 4 - 5 - null要求你把它变成 5 - 4 - 3 - 2 - 1 - null。注意这里的难点不在「倒序」而在「单向」两个字。数组可以下标随便跳着访问我先读最后一位、再读倒数第二位随便怎么倒都行链表不行每个节点只知道自己的下一个是谁不知道上一个是谁一旦你把某个节点的 next 改掉通向后面的路就断了。这就是链表反转的唯一核心矛盾改指向和保住后路必须同时进行。你手里永远需要至少两个信息——「我已经处理完的那一段的头」和「还没处理的那一段的头」。想清楚这一点三种解法的差异其实只是「用变量保存」还是「用函数调用栈保存」而已。真实工程里这个操作也不是纯练习题。浏览器历史记录的前进后退、播放器的上一首下一首、撤销操作栈、某些 LRU 缓存的内部实现底层都是双向链表或者带前后指针的结构。而反转这个动作本身在数据迁移、日志回溯、批处理队列翻转这类场景里很常见。只不过工程里我们通常用标准库容器或者直接反转数组手写链表反转更多是面试和思维训练。1.2 三种解法的选型为什么迭代版是首选我在不同阶段写过三种实现各自的定位很清楚。第一种是双指针迭代法也叫三指针法。用 prev、cur、nxt 三个变量在一条循环里往前走边走边把 cur-next 掉头指向 prev。时间复杂度 O(n)空间复杂度 O(1)代码八行左右。这是默认答案面试第一版就该写它因为它的空间复杂度是最优的而且不依赖调用栈几百上千万节点的链表也不会崩。第二种是递归法。思路很优雅先把 head-next 之后的整条链反转好拿到反转后的新头节点再处理当前这个 head 该接到哪儿。代码短到五行但它的空间复杂度是 O(n)因为每一层递归都要占用一个栈帧。优雅的代价是深度限制——这一点我在第四节会给出实测数据。第三种是虚拟头结点 头插法。建一个假的头节点 dummy然后遍历原链表每读一个节点就把它插到 dummy 后面。这种「头插」的思路通用性极强后面做区间反转、K 个一组反转、重排链表基本都靠它打底。缺点是稍微抽象一点得多看两遍才顺眼。为什么我不建议新手一上来就背递归版因为递归版把「指针怎么走」这件事藏进了函数调用栈你写对了也说不清楚为什么对写错了更难调试。而迭代版是把每一步都摊在明面上哪一步漏了立刻就暴露出来学习效率高得多。先把迭代写熟递归自然就懂了。1.3 面试里真正会被追问的点我面过几次也被人面过几次这道 Easy 题的追问套路其实很固定提前想清楚能省很多临场慌。面试官大概率会问能不能只用 O(1) 空间这是在验证你会不会一上来就写递归。还会问如果链表里有一个环怎么办这其实是在问你会不会判断终止条件反转带环的链表本身就是个无解或者需要先检测的定义问题你得先说出「先判断有没有环」。另一个高频追问是能不能不改 next 指针只交换节点里的值这个问题的答案是能用数组把值抄下来倒着填回去就行但你要主动说明这样做的空间是 O(n)面试官通常只是想看看你会不会读题。还有一个容易被忽略的细节节点里的数据太大怎么办如果节点存的是一个几 KB 的结构体交换值就是一笔不小的拷贝开销这时候改指针明显更划算。这算是从算法题延伸到工程判断的一个小加分点。2. 核心细节解析指针三兄弟的顺序不能乱2.1 迭代法的四步走顺序错了立刻断链迭代版的循环体里就四行但这四行有严格的先后顺序我把它标出来。ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; ListNode* cur head; while (cur ! nullptr) { ListNode* nxt cur-next; // 第一步存后路 cur-next prev; // 第二步掉头 prev cur; // 第三步prev 前进 cur nxt; // 第四步cur 前进 } return prev; }先说初始状态为什么是prev nullptr。反转之后原来链表的第一个节点会变成最后一个节点而最后一个节点的 next 必须是 null所以 prev 从空开始第一轮循环正好把第一个节点的 next 置空。这是很多人的第一个坑把 prev 初始化成 head结果链表尾部自己指向自己程序直接死循环。第一步存后路绝对不能省也不能挪到后面。假设你写完cur-next prev之后才想起来要保存 nxt那cur-next已经被你改成 prev 了你拿到的 nxt 就是 prev整条链瞬间断成孤岛。我见过有人试图用「先记录 head-next-next」这种写法绕过去逻辑上偶尔能对但只要链表长度是 1 或者 2 就立刻越界访问不推荐。第三步和第四步的顺序同样有讲究。必须先把 prev 推到 cur 当前位置再把 cur 推到 nxt。如果反过来先推 curprev 就会停在原地不动最后返回的 prev 是错的。这四行我一般让学生默念成一句话先留后路再掉头然后两个人一起往前走。返回值为什么是 prev 而不是 cur循环结束时 cur 是 nullptrprev 停在原来的尾节点上也就是反转后的新头。我第一次写的时候返回了 head结果输出只有一个节点排查了十几分钟才反应过来——head 早就变成链表尾巴了。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 nullptr是防空链表head-next nullptr是防单节点链表。如果只写前者遇到只有一个节点的链表时会继续递归到空指针上然后崩在解引用上。核心就两行。以 1 - 2 - 3 - null 为例调用栈一路压到最深处返回的是 3 这个节点。回溯到 head 为 2 的那一层时head-next指向 3所以head-next-next head就是把 3 的 next 指回 2完成了 3 - 2 的掉头紧接着head-next nullptr把 2 原来的 next 清掉防止成环。等回到最外层 head 为 1 的那一层head-next已经是 2 了于是 2 的 next 指向 11 的 next 置空最终得到 3 - 2 - 1 - null。这两行的顺序不能换。如果先写head-next nullptr那head-next-next就变成对空指针解引用直接段错误。至于返回值每一层都往上传同一个 newHead也就是最深一层返回的那个原尾节点这个设计挺巧妙的不要试图改成返回 head。递归版最容易让人困惑的地方是「我明明在往前递归为什么指针是往回指的」。你可以这样理解递归的过程是在找尾巴找的过程不做事找到了之后顺着返回的路一层层收拾每次把当前节点接到自己后继的后面。这就是典型的后序遍历思路。2.3 节点定义与本地自测的内存问题工程里手写链表节点定义基本固定成这样struct ListNode { int val; ListNode* next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode* n) : val(x), next(n) {} };这里有个新手经常踩的坑如果你偷懒写一个只声明int val; ListNode* next;的结构体然后在本地用例里手动ListNode node; node.val 1;那么 node.next 是未初始化的一块内存值是随机的。你可能运气好跑出正确结果也可能随机崩掉甚至在某些环境里稳定复现不了。所以构造函数一定要把 next 初始化成 nullptr这不是代码风格问题是正确性问题。另一个问题是内存所有权。在 LeetCode 这类平台上节点由判题机创建和销毁你只负责改指针不用管释放。但在本地自测时你用 new 创建的节点谁释放我的习惯是写一个简单的清理函数在测试结束后把链表遍历一遍挨个 delete。别嫌麻烦做几百次测试的时候如果不释放内存占用会一直涨还会掩盖真实的内存问题。当然如果你只是跑几个小用例泄漏点也无所谓但养成习惯总没坏处。还有个细节反转之后原来那条链的「头指针」变量如果没更新它仍然指向原链表的第一个节点而现在那个节点是尾巴。这些悬空的引用在单线程小测试里不会出问题但在真实系统里就是逻辑 bug。所以函数的返回值一定要用不要图省事继续用旧变量。3. 实操过程从建文件到跑通全流程3.1 环境准备和编译命令我本机是 VSCode gMinGW-w64 或者 Linux 下的 GCC 都行写算法题不需要复杂的工程结构一个 cpp 文件加一个终端就够。如果你还没配好环境简单说需要三样东西编译器、编辑器、终端。Windows 下装 MinGW-w64 然后把 bin 目录加到 PATHLinux 直接用包管理器装 build-essentialmacOS 装 Xcode Command Line Tools。编译命令我一般这么敲顺手把常用开关全带上g -stdc17 -O2 -Wall -Wextra -g reverse_list.cpp -o rl ./rl几个开关的作用值得说清楚。-stdc17保证语言版本一致避免本地能编译、换台机器就不行。-Wall -Wextra打开警告很多低级错误比如「变量未使用」「有符号无符号比较」会直接提示你。-g保留调试符号方便 gdb 断点。-O2开优化做性能测试时必须加不然测出来的时间没有参考意义。调试野指针的时候我会额外挂上 sanitizerg -stdc17 -g -fsanitizeaddress,undefined -fno-omit-frame-pointer reverse_list.cpp -o rl_dbg ./rl_dbgAddressSanitizer 能在你越界读写或者用已释放内存的时候直接打印出出错的代码行和内存地址比盯着输出瞎猜快十倍。唯一的代价是运行变慢、内存占用变高所以只在调试时开。3.2 手写一个能复用的自测脚手架写算法题最省时间的一个习惯是给链表题准备两个工具函数一个把数组转成链表一个把链表打印成字符串。这两行代码写一次能用一整年。#include bits/stdc.h using namespace std; ListNode* build(const vectorint v) { ListNode dummy(0); ListNode* tail dummy; for (int x : v) { tail-next new ListNode(x); tail tail-next; } return dummy.next; } string dump(ListNode* h) { string s; while (h) { s to_string(h-val) -; h h-next; } return s null; }build里用了栈上的 dummy 节点做哨兵这样就不用为首节点单独写 if 分支返回值是 dummy.next。这个「哨兵节点」技巧在链表题里出现频率极高后面讲区间反转还会用到先在这里建立印象。dump顺便还能当环检测用。如果你不小心把链表搞成了环dump 会一直打印下去不结束这本身就是个信号——当然更规范的做法是加一个步数上限超过一定数量就判为有环string dump(ListNode* h, int limit 1000) { string s; int cnt 0; while (h cnt limit) { s to_string(h-val) -; h h-next; } if (h) s [可能有环]; return s null; }3.3 完整可跑的主函数与结果验证把上面这些东西拼起来主函数长这样int main() { vectorvectorint cases { {}, // 空链表 {1}, // 单节点 {1, 2}, // 两节点 {1, 2, 3, 4, 5}, // 常规 }; for (auto c : cases) { ListNode* h build(c); cout 输入: dump(h) endl; ListNode* r1 reverseList(h); cout 迭代: dump(r1) endl; ListNode* h2 build(c); ListNode* r2 reverseListRec(h2); cout 递归: dump(r2) endl; cout --- endl; } return 0; }我把空链表和单节点这两个边界放进用例里是有原因的。绝大多数人写反转头几次翻车都翻在这两种输入上。空链表走迭代版时 while 循环一次都不进直接返回 prev 也就是 nullptr看着没问题但如果你的终止条件写成了while (cur-next)空链表直接解引用空指针。单节点的情况则考验你的 prev 初始化对不对把它自己指向自己就完蛋。跑出来的输出应该是这样输入: 1-2-3-4-5-null 迭代: 5-4-3-2-1-null 递归: 5-4-3-2-1-null两边结果一致说明两种实现都正确。这个「同一组用例跑多种实现、对比输出」的模式我强烈建议在刷题初期坚持用它比在平台上提交一次看一次红绿要高效得多。3.4 从这道题改写出区间反转和 K 个一组反转真正检验你有没有理解指针操作的是这道题的变体。先说区间反转给你 left 和 right 两个位置只反转这个区间内的节点。ListNode* reverseBetween(ListNode* head, int left, int right) { ListNode dummy(0); dummy.next head; ListNode* pre dummy; for (int i 1; i left; i) pre pre-next; ListNode* cur pre-next; for (int i 0; i right - left; i) { ListNode* nxt cur-next; cur-next nxt-next; nxt-next pre-next; pre-next nxt; } return dummy.next; }这里的思路和整体反转不太一样用的是「把后面的节点不断插到前面来」。pre 固定在区间前一个位置不动cur 固定在区间第一个位置不动每一轮把 cur 的后继节点摘下来插到 pre-next 的位置。循环right - left次之后区间内就自然逆序了。这个方法的好处是不用记录前后四个边界指针省掉了大量容易出错的赋值。再说 K 个一组反转这是面试里出现频率很高的进阶题。思路是每 k 个节点做一次局部反转然后把各段接起来。递归写法最清晰ListNode* reverseKGroup(ListNode* head, int k) { ListNode* node head; for (int i 0; i k; i) { if (!node) return head; // 不足 k 个保持原样 node node-next; } ListNode* prev nullptr; ListNode* cur head; for (int i 0; i k; i) { ListNode* nxt cur-next; cur-next prev; prev cur; cur nxt; } head-next reverseKGroup(cur, k); return prev; }开头那个 for 循环是「探路」先确认剩下够不够 k 个。这一步千万别省不然最后一组不足 k 个的时候你也会把它反转结果就错了。另外注意反转完之后 head 已经变成这一段的尾巴了所以要让head-next指向下一组的处理结果这个方向和直觉是反的多写几遍就顺了。4. 常见问题与排查技巧实录4.1 报错速查表下面这张表是我自己踩过、也帮别人看过的问题集合按现象分类出问题的时候可以直接对号入座。现象大概率原因修法输出只剩一个节点循环里没保存 nxt先改了 next把nxt cur-next提到赋值之前返回的头节点是原链表的头返回值写了 head 而不是 prev返回 prev或用哨兵节点程序一直不结束输出无限重复链表成了环通常是尾节点没置空用带步数上限的 dump 定位检查尾节点 next空链表输入直接崩溃循环条件用了cur-next改成cur ! nullptr单节点输入结果变成自环prev 初始化成了 head初始化为 nullptr递归版在长链表上段错误递归深度超过栈容量改用迭代版或增大栈本地崩溃平台通过本地节点未初始化 next补全构造函数next默认 nullptr用 ASan 报 heap-buffer-overflow访问了已释放或越界节点检查 delete 之后有没有继续用指针4.2 调试三板斧画图、打日志、开 sanitizer第一板斧是画图。链表题的调试纸上画三个方框代表 prev、cur、nxt每执行一行就在图上动一次。听起来很笨但对理解指针变化极其有效我初学阶段平均每道链表题要画两三张纸。等你画到不用画就能在脑子里演算说明这个模型真的进去了。第二板斧是打日志。在循环里插一行打印能直接看到每一轮的状态while (cur) { ListNode* nxt cur-next; cur-next prev; prev cur; cur nxt; cout prev (prev ? prev-val : -1) cur (cur ? cur-val : -1) endl; }这里有个小坑打印的时候必须判空因为链表反转过程中游走指针很容易跑到 nullptr 上直接prev-val就是空指针解引用。写成三元表达式虽然啰嗦但省心。第三板斧是开 sanitizer也就是上面那条编译命令。它最擅长抓的是「用了已经 delete 掉的节点」和「访问越界」这两类问题而这恰好是手写链表最容易犯、又最难靠肉眼看出来的错误。我在本地做批量测试的时候默认开着它代价是慢但换来的安心值这个价。4.3 迭代和递归的性能实测数据我在本机用 chrono 做了一个简单的对比测试链表长度取 100 万节点值用递增整数各跑十次取平均。实现方式时间复杂度空间复杂度100 万节点耗时备注双指针迭代O(n)O(1)约 8~12 ms稳定无深度限制递归O(n)O(n)约 15~20 ms约 8 万节点开始有爆栈风险头插法哨兵O(n)O(1)约 10~14 ms比标准迭代略慢指针写得多关于递归的爆栈阈值我实测下来大约在 8 万层左右开始出现段错误这个数字和栈大小、编译器优化、每层栈帧的实际大小都有关不同机器上会有差异不要当成固定值。但结论是确定的链表长度可能上万的时候递归版不能用在生产代码里。这也是为什么面试官听到你说「我用递归空间 O(n)」之后往往会追一句「能不能优化到 O(1)」。耗时数据里有一处可能反直觉头插法比标准迭代略慢。原因是标准迭代每轮只改一次 next而头插法每轮要改两次指针写内存的次数更多。在百万量级下这点差异体现在时间上量级小的时候完全看不出来。所以你选哪一种主要看可读性和后续扩展不用为了这几毫秒纠结。注意做性能测试一定不要忘记加 -O2。我第一版测试忘了加优化迭代版测出来 80 ms差点以为是代码写得有问题加上 -O2 之后掉到 10 ms 以内结论完全反过来了。5. 从这一题延伸出去的刷题路线5.1 配套必刷的几道链表题反转链表是个枢纽题它的变体和后续题非常密集。我自己是按这个顺序刷的从易到难每一道都建立在前一道的指针手感上。第一道是判断回文链表。核心做法是快慢指针找中点把后半段反转然后两段同步比较。你会发现后半段反转这一步就是本文的题所以刷完反转再来做这道基本就是拼积木。第二道是重排链表形如 L0 - L1 - ... - Ln 变成 L0 - Ln - L1 - Ln-1。做法还是找中点、反转后半段、再交替合并和回文链表共享百分之七十的代码。第三道是两两交换链表节点本质上是 K 2 的分组反转写完 K 个一组之后这道题就是三行改动。第四道是合并两个有序链表第五道是删除倒数第 N 个节点这两道主要练哨兵节点和快慢指针的配合。第六道是复制带随机指针的链表难度上了一个台阶需要哈希表或者原地穿插的思路属于链表章节的分水岭。5.2 我自己的复习节奏最后聊点方法层面的东西。链表题的手感非常依赖短期记忆我如果两周不碰再写反转的时候还是会把 nxt 那行的位置写错。所以我的做法是新题刷完之后隔三天、隔一周、隔一个月各重写一次只重写不重看写完编译跑用例。能一次过就跳过卡壳就标记出来重点回炉。另一个有用的习惯是写完代码之后强制口述一遍。对着空气说「prev 从空开始因为反转后第一个节点要指向空nxt 必须在改指针之前保存否则后路断了」。这个过程能暴露你到底是真懂了还是背下来的。我试过几次之后发现有些题我能敲出正确代码但讲不清理由那基本就属于肌肉记忆面试稍微变个形就露馅。还有一个不太有人提的点C 写链表题的时候尽量把ListNode*的星号贴着变量名写别贴类型名。原因不复杂ListNode* a, b;这行里只有 a 是指针b 是对象如果你习惯了星号贴类型很容易在这种多变量声明上翻车。链表题里清一色是指针把这个习惯养好能少踩不少坑。链表这一章说到底就是在练一件事在信息只能单向流动的结构上如何安全地重排连接关系。把 Reverse Linked List 这道 Easy 题彻底吃透把每一行指针的动机都讲清楚后面那些看起来吓人的 Hard 链表题拆开来看无非就是这段八行循环的组合与嵌套。
C++ 反转链表：迭代、递归、头插法与面试扩展
上周三晚上十一点多一个刚转方向学 C 的朋友给我发消息说 Reverse Linked List 这道题他看了三遍题解合上编辑器还是写不对指针一改就断链。这事儿我太熟了——链表反转是算法题里少见的「代码不到十行、坑却有一箩筐」的典型难度标记 Easy但真正能一次性写对、并且讲清楚每一行指针为什么这么动的人比例并不高。这篇记录来自我自己刷 C 算法题时留下的笔记围绕 Reverse Linked List反转链表这道 Easy 题展开。我会把迭代、递归、头插法三种写法逐行拆开把本地自测环境的搭建、编译命令、常见报错的排查过程都写进去再顺手把它延伸出去的区间反转、K 个一组反转一起串一遍。它不是给判题机交作业用的答案而是一份能落地复现的工程笔记你在 VSCode 里新建一个 .cpp 文件照着敲一遍就能在本机跑出结果、看到每一轮指针的变化。适合谁看如果你刚学完 C 的结构体和指针还没真正搞明白「指针的指针在什么位置被改写」这篇能帮你把地基夯一遍如果你已经能默写迭代版但一到递归版本就卡壳或者面试被追问「能不能 O(1) 空间」「K 个一组怎么处理」第三、第四节的细节和排查表会让你少走很多弯路。链表这块东西没有花哨的数学考的就是对指针、边界、内存这三个东西的掌控力而这三样恰好是 C 的基本功。1. 整体设计与思路拆解先想清楚要动什么1.1 反转链表到底在解决什么问题把问题翻译成人话给你一条单向链表比如 1 - 2 - 3 - 4 - 5 - null要求你把它变成 5 - 4 - 3 - 2 - 1 - null。注意这里的难点不在「倒序」而在「单向」两个字。数组可以下标随便跳着访问我先读最后一位、再读倒数第二位随便怎么倒都行链表不行每个节点只知道自己的下一个是谁不知道上一个是谁一旦你把某个节点的 next 改掉通向后面的路就断了。这就是链表反转的唯一核心矛盾改指向和保住后路必须同时进行。你手里永远需要至少两个信息——「我已经处理完的那一段的头」和「还没处理的那一段的头」。想清楚这一点三种解法的差异其实只是「用变量保存」还是「用函数调用栈保存」而已。真实工程里这个操作也不是纯练习题。浏览器历史记录的前进后退、播放器的上一首下一首、撤销操作栈、某些 LRU 缓存的内部实现底层都是双向链表或者带前后指针的结构。而反转这个动作本身在数据迁移、日志回溯、批处理队列翻转这类场景里很常见。只不过工程里我们通常用标准库容器或者直接反转数组手写链表反转更多是面试和思维训练。1.2 三种解法的选型为什么迭代版是首选我在不同阶段写过三种实现各自的定位很清楚。第一种是双指针迭代法也叫三指针法。用 prev、cur、nxt 三个变量在一条循环里往前走边走边把 cur-next 掉头指向 prev。时间复杂度 O(n)空间复杂度 O(1)代码八行左右。这是默认答案面试第一版就该写它因为它的空间复杂度是最优的而且不依赖调用栈几百上千万节点的链表也不会崩。第二种是递归法。思路很优雅先把 head-next 之后的整条链反转好拿到反转后的新头节点再处理当前这个 head 该接到哪儿。代码短到五行但它的空间复杂度是 O(n)因为每一层递归都要占用一个栈帧。优雅的代价是深度限制——这一点我在第四节会给出实测数据。第三种是虚拟头结点 头插法。建一个假的头节点 dummy然后遍历原链表每读一个节点就把它插到 dummy 后面。这种「头插」的思路通用性极强后面做区间反转、K 个一组反转、重排链表基本都靠它打底。缺点是稍微抽象一点得多看两遍才顺眼。为什么我不建议新手一上来就背递归版因为递归版把「指针怎么走」这件事藏进了函数调用栈你写对了也说不清楚为什么对写错了更难调试。而迭代版是把每一步都摊在明面上哪一步漏了立刻就暴露出来学习效率高得多。先把迭代写熟递归自然就懂了。1.3 面试里真正会被追问的点我面过几次也被人面过几次这道 Easy 题的追问套路其实很固定提前想清楚能省很多临场慌。面试官大概率会问能不能只用 O(1) 空间这是在验证你会不会一上来就写递归。还会问如果链表里有一个环怎么办这其实是在问你会不会判断终止条件反转带环的链表本身就是个无解或者需要先检测的定义问题你得先说出「先判断有没有环」。另一个高频追问是能不能不改 next 指针只交换节点里的值这个问题的答案是能用数组把值抄下来倒着填回去就行但你要主动说明这样做的空间是 O(n)面试官通常只是想看看你会不会读题。还有一个容易被忽略的细节节点里的数据太大怎么办如果节点存的是一个几 KB 的结构体交换值就是一笔不小的拷贝开销这时候改指针明显更划算。这算是从算法题延伸到工程判断的一个小加分点。2. 核心细节解析指针三兄弟的顺序不能乱2.1 迭代法的四步走顺序错了立刻断链迭代版的循环体里就四行但这四行有严格的先后顺序我把它标出来。ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; ListNode* cur head; while (cur ! nullptr) { ListNode* nxt cur-next; // 第一步存后路 cur-next prev; // 第二步掉头 prev cur; // 第三步prev 前进 cur nxt; // 第四步cur 前进 } return prev; }先说初始状态为什么是prev nullptr。反转之后原来链表的第一个节点会变成最后一个节点而最后一个节点的 next 必须是 null所以 prev 从空开始第一轮循环正好把第一个节点的 next 置空。这是很多人的第一个坑把 prev 初始化成 head结果链表尾部自己指向自己程序直接死循环。第一步存后路绝对不能省也不能挪到后面。假设你写完cur-next prev之后才想起来要保存 nxt那cur-next已经被你改成 prev 了你拿到的 nxt 就是 prev整条链瞬间断成孤岛。我见过有人试图用「先记录 head-next-next」这种写法绕过去逻辑上偶尔能对但只要链表长度是 1 或者 2 就立刻越界访问不推荐。第三步和第四步的顺序同样有讲究。必须先把 prev 推到 cur 当前位置再把 cur 推到 nxt。如果反过来先推 curprev 就会停在原地不动最后返回的 prev 是错的。这四行我一般让学生默念成一句话先留后路再掉头然后两个人一起往前走。返回值为什么是 prev 而不是 cur循环结束时 cur 是 nullptrprev 停在原来的尾节点上也就是反转后的新头。我第一次写的时候返回了 head结果输出只有一个节点排查了十几分钟才反应过来——head 早就变成链表尾巴了。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 nullptr是防空链表head-next nullptr是防单节点链表。如果只写前者遇到只有一个节点的链表时会继续递归到空指针上然后崩在解引用上。核心就两行。以 1 - 2 - 3 - null 为例调用栈一路压到最深处返回的是 3 这个节点。回溯到 head 为 2 的那一层时head-next指向 3所以head-next-next head就是把 3 的 next 指回 2完成了 3 - 2 的掉头紧接着head-next nullptr把 2 原来的 next 清掉防止成环。等回到最外层 head 为 1 的那一层head-next已经是 2 了于是 2 的 next 指向 11 的 next 置空最终得到 3 - 2 - 1 - null。这两行的顺序不能换。如果先写head-next nullptr那head-next-next就变成对空指针解引用直接段错误。至于返回值每一层都往上传同一个 newHead也就是最深一层返回的那个原尾节点这个设计挺巧妙的不要试图改成返回 head。递归版最容易让人困惑的地方是「我明明在往前递归为什么指针是往回指的」。你可以这样理解递归的过程是在找尾巴找的过程不做事找到了之后顺着返回的路一层层收拾每次把当前节点接到自己后继的后面。这就是典型的后序遍历思路。2.3 节点定义与本地自测的内存问题工程里手写链表节点定义基本固定成这样struct ListNode { int val; ListNode* next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode* n) : val(x), next(n) {} };这里有个新手经常踩的坑如果你偷懒写一个只声明int val; ListNode* next;的结构体然后在本地用例里手动ListNode node; node.val 1;那么 node.next 是未初始化的一块内存值是随机的。你可能运气好跑出正确结果也可能随机崩掉甚至在某些环境里稳定复现不了。所以构造函数一定要把 next 初始化成 nullptr这不是代码风格问题是正确性问题。另一个问题是内存所有权。在 LeetCode 这类平台上节点由判题机创建和销毁你只负责改指针不用管释放。但在本地自测时你用 new 创建的节点谁释放我的习惯是写一个简单的清理函数在测试结束后把链表遍历一遍挨个 delete。别嫌麻烦做几百次测试的时候如果不释放内存占用会一直涨还会掩盖真实的内存问题。当然如果你只是跑几个小用例泄漏点也无所谓但养成习惯总没坏处。还有个细节反转之后原来那条链的「头指针」变量如果没更新它仍然指向原链表的第一个节点而现在那个节点是尾巴。这些悬空的引用在单线程小测试里不会出问题但在真实系统里就是逻辑 bug。所以函数的返回值一定要用不要图省事继续用旧变量。3. 实操过程从建文件到跑通全流程3.1 环境准备和编译命令我本机是 VSCode gMinGW-w64 或者 Linux 下的 GCC 都行写算法题不需要复杂的工程结构一个 cpp 文件加一个终端就够。如果你还没配好环境简单说需要三样东西编译器、编辑器、终端。Windows 下装 MinGW-w64 然后把 bin 目录加到 PATHLinux 直接用包管理器装 build-essentialmacOS 装 Xcode Command Line Tools。编译命令我一般这么敲顺手把常用开关全带上g -stdc17 -O2 -Wall -Wextra -g reverse_list.cpp -o rl ./rl几个开关的作用值得说清楚。-stdc17保证语言版本一致避免本地能编译、换台机器就不行。-Wall -Wextra打开警告很多低级错误比如「变量未使用」「有符号无符号比较」会直接提示你。-g保留调试符号方便 gdb 断点。-O2开优化做性能测试时必须加不然测出来的时间没有参考意义。调试野指针的时候我会额外挂上 sanitizerg -stdc17 -g -fsanitizeaddress,undefined -fno-omit-frame-pointer reverse_list.cpp -o rl_dbg ./rl_dbgAddressSanitizer 能在你越界读写或者用已释放内存的时候直接打印出出错的代码行和内存地址比盯着输出瞎猜快十倍。唯一的代价是运行变慢、内存占用变高所以只在调试时开。3.2 手写一个能复用的自测脚手架写算法题最省时间的一个习惯是给链表题准备两个工具函数一个把数组转成链表一个把链表打印成字符串。这两行代码写一次能用一整年。#include bits/stdc.h using namespace std; ListNode* build(const vectorint v) { ListNode dummy(0); ListNode* tail dummy; for (int x : v) { tail-next new ListNode(x); tail tail-next; } return dummy.next; } string dump(ListNode* h) { string s; while (h) { s to_string(h-val) -; h h-next; } return s null; }build里用了栈上的 dummy 节点做哨兵这样就不用为首节点单独写 if 分支返回值是 dummy.next。这个「哨兵节点」技巧在链表题里出现频率极高后面讲区间反转还会用到先在这里建立印象。dump顺便还能当环检测用。如果你不小心把链表搞成了环dump 会一直打印下去不结束这本身就是个信号——当然更规范的做法是加一个步数上限超过一定数量就判为有环string dump(ListNode* h, int limit 1000) { string s; int cnt 0; while (h cnt limit) { s to_string(h-val) -; h h-next; } if (h) s [可能有环]; return s null; }3.3 完整可跑的主函数与结果验证把上面这些东西拼起来主函数长这样int main() { vectorvectorint cases { {}, // 空链表 {1}, // 单节点 {1, 2}, // 两节点 {1, 2, 3, 4, 5}, // 常规 }; for (auto c : cases) { ListNode* h build(c); cout 输入: dump(h) endl; ListNode* r1 reverseList(h); cout 迭代: dump(r1) endl; ListNode* h2 build(c); ListNode* r2 reverseListRec(h2); cout 递归: dump(r2) endl; cout --- endl; } return 0; }我把空链表和单节点这两个边界放进用例里是有原因的。绝大多数人写反转头几次翻车都翻在这两种输入上。空链表走迭代版时 while 循环一次都不进直接返回 prev 也就是 nullptr看着没问题但如果你的终止条件写成了while (cur-next)空链表直接解引用空指针。单节点的情况则考验你的 prev 初始化对不对把它自己指向自己就完蛋。跑出来的输出应该是这样输入: 1-2-3-4-5-null 迭代: 5-4-3-2-1-null 递归: 5-4-3-2-1-null两边结果一致说明两种实现都正确。这个「同一组用例跑多种实现、对比输出」的模式我强烈建议在刷题初期坚持用它比在平台上提交一次看一次红绿要高效得多。3.4 从这道题改写出区间反转和 K 个一组反转真正检验你有没有理解指针操作的是这道题的变体。先说区间反转给你 left 和 right 两个位置只反转这个区间内的节点。ListNode* reverseBetween(ListNode* head, int left, int right) { ListNode dummy(0); dummy.next head; ListNode* pre dummy; for (int i 1; i left; i) pre pre-next; ListNode* cur pre-next; for (int i 0; i right - left; i) { ListNode* nxt cur-next; cur-next nxt-next; nxt-next pre-next; pre-next nxt; } return dummy.next; }这里的思路和整体反转不太一样用的是「把后面的节点不断插到前面来」。pre 固定在区间前一个位置不动cur 固定在区间第一个位置不动每一轮把 cur 的后继节点摘下来插到 pre-next 的位置。循环right - left次之后区间内就自然逆序了。这个方法的好处是不用记录前后四个边界指针省掉了大量容易出错的赋值。再说 K 个一组反转这是面试里出现频率很高的进阶题。思路是每 k 个节点做一次局部反转然后把各段接起来。递归写法最清晰ListNode* reverseKGroup(ListNode* head, int k) { ListNode* node head; for (int i 0; i k; i) { if (!node) return head; // 不足 k 个保持原样 node node-next; } ListNode* prev nullptr; ListNode* cur head; for (int i 0; i k; i) { ListNode* nxt cur-next; cur-next prev; prev cur; cur nxt; } head-next reverseKGroup(cur, k); return prev; }开头那个 for 循环是「探路」先确认剩下够不够 k 个。这一步千万别省不然最后一组不足 k 个的时候你也会把它反转结果就错了。另外注意反转完之后 head 已经变成这一段的尾巴了所以要让head-next指向下一组的处理结果这个方向和直觉是反的多写几遍就顺了。4. 常见问题与排查技巧实录4.1 报错速查表下面这张表是我自己踩过、也帮别人看过的问题集合按现象分类出问题的时候可以直接对号入座。现象大概率原因修法输出只剩一个节点循环里没保存 nxt先改了 next把nxt cur-next提到赋值之前返回的头节点是原链表的头返回值写了 head 而不是 prev返回 prev或用哨兵节点程序一直不结束输出无限重复链表成了环通常是尾节点没置空用带步数上限的 dump 定位检查尾节点 next空链表输入直接崩溃循环条件用了cur-next改成cur ! nullptr单节点输入结果变成自环prev 初始化成了 head初始化为 nullptr递归版在长链表上段错误递归深度超过栈容量改用迭代版或增大栈本地崩溃平台通过本地节点未初始化 next补全构造函数next默认 nullptr用 ASan 报 heap-buffer-overflow访问了已释放或越界节点检查 delete 之后有没有继续用指针4.2 调试三板斧画图、打日志、开 sanitizer第一板斧是画图。链表题的调试纸上画三个方框代表 prev、cur、nxt每执行一行就在图上动一次。听起来很笨但对理解指针变化极其有效我初学阶段平均每道链表题要画两三张纸。等你画到不用画就能在脑子里演算说明这个模型真的进去了。第二板斧是打日志。在循环里插一行打印能直接看到每一轮的状态while (cur) { ListNode* nxt cur-next; cur-next prev; prev cur; cur nxt; cout prev (prev ? prev-val : -1) cur (cur ? cur-val : -1) endl; }这里有个小坑打印的时候必须判空因为链表反转过程中游走指针很容易跑到 nullptr 上直接prev-val就是空指针解引用。写成三元表达式虽然啰嗦但省心。第三板斧是开 sanitizer也就是上面那条编译命令。它最擅长抓的是「用了已经 delete 掉的节点」和「访问越界」这两类问题而这恰好是手写链表最容易犯、又最难靠肉眼看出来的错误。我在本地做批量测试的时候默认开着它代价是慢但换来的安心值这个价。4.3 迭代和递归的性能实测数据我在本机用 chrono 做了一个简单的对比测试链表长度取 100 万节点值用递增整数各跑十次取平均。实现方式时间复杂度空间复杂度100 万节点耗时备注双指针迭代O(n)O(1)约 8~12 ms稳定无深度限制递归O(n)O(n)约 15~20 ms约 8 万节点开始有爆栈风险头插法哨兵O(n)O(1)约 10~14 ms比标准迭代略慢指针写得多关于递归的爆栈阈值我实测下来大约在 8 万层左右开始出现段错误这个数字和栈大小、编译器优化、每层栈帧的实际大小都有关不同机器上会有差异不要当成固定值。但结论是确定的链表长度可能上万的时候递归版不能用在生产代码里。这也是为什么面试官听到你说「我用递归空间 O(n)」之后往往会追一句「能不能优化到 O(1)」。耗时数据里有一处可能反直觉头插法比标准迭代略慢。原因是标准迭代每轮只改一次 next而头插法每轮要改两次指针写内存的次数更多。在百万量级下这点差异体现在时间上量级小的时候完全看不出来。所以你选哪一种主要看可读性和后续扩展不用为了这几毫秒纠结。注意做性能测试一定不要忘记加 -O2。我第一版测试忘了加优化迭代版测出来 80 ms差点以为是代码写得有问题加上 -O2 之后掉到 10 ms 以内结论完全反过来了。5. 从这一题延伸出去的刷题路线5.1 配套必刷的几道链表题反转链表是个枢纽题它的变体和后续题非常密集。我自己是按这个顺序刷的从易到难每一道都建立在前一道的指针手感上。第一道是判断回文链表。核心做法是快慢指针找中点把后半段反转然后两段同步比较。你会发现后半段反转这一步就是本文的题所以刷完反转再来做这道基本就是拼积木。第二道是重排链表形如 L0 - L1 - ... - Ln 变成 L0 - Ln - L1 - Ln-1。做法还是找中点、反转后半段、再交替合并和回文链表共享百分之七十的代码。第三道是两两交换链表节点本质上是 K 2 的分组反转写完 K 个一组之后这道题就是三行改动。第四道是合并两个有序链表第五道是删除倒数第 N 个节点这两道主要练哨兵节点和快慢指针的配合。第六道是复制带随机指针的链表难度上了一个台阶需要哈希表或者原地穿插的思路属于链表章节的分水岭。5.2 我自己的复习节奏最后聊点方法层面的东西。链表题的手感非常依赖短期记忆我如果两周不碰再写反转的时候还是会把 nxt 那行的位置写错。所以我的做法是新题刷完之后隔三天、隔一周、隔一个月各重写一次只重写不重看写完编译跑用例。能一次过就跳过卡壳就标记出来重点回炉。另一个有用的习惯是写完代码之后强制口述一遍。对着空气说「prev 从空开始因为反转后第一个节点要指向空nxt 必须在改指针之前保存否则后路断了」。这个过程能暴露你到底是真懂了还是背下来的。我试过几次之后发现有些题我能敲出正确代码但讲不清理由那基本就属于肌肉记忆面试稍微变个形就露馅。还有一个不太有人提的点C 写链表题的时候尽量把ListNode*的星号贴着变量名写别贴类型名。原因不复杂ListNode* a, b;这行里只有 a 是指针b 是对象如果你习惯了星号贴类型很容易在这种多变量声明上翻车。链表题里清一色是指针把这个习惯养好能少踩不少坑。链表这一章说到底就是在练一件事在信息只能单向流动的结构上如何安全地重排连接关系。把 Reverse Linked List 这道 Easy 题彻底吃透把每一行指针的动机都讲清楚后面那些看起来吓人的 Hard 链表题拆开来看无非就是这段八行循环的组合与嵌套。
![基于vue的儿童福利院管理系统[Vue]-计算机毕业设计源码+LW文档](http://pic.xiahunao.cn/yaotu/基于vue的儿童福利院管理系统[Vue]-计算机毕业设计源码+LW文档)
