反转链表：机试高频题的迭代与递归解法全拆解

1. 这道题为什么是机试的“钉子户”做了几年面试官也刷过几百道题我越来越能理解为什么“反转链表”能成为机试环节的钉子户。它不像动态规划那样需要敏锐的模型抽象能力也不像红黑树那样考验庞大的知识储备但它恰好卡在“基础扎实程度”和“边界条件意识”之间的缝隙里。很多人觉得这题烂大街不屑于准备结果在真正的考场上反而写得磕磕绊绊甚至当场翻车。1.1 从面试官视角看反转链表如果你站在面试官的角度会发现反转链表是一道性价比极高的题目。它能在五分钟内考察出四件事第一你知不知道链表节点该怎么定义第二你有没有真正理解指针/引用的含义——是变量本身还是地址第三你能不能在不借助额外容器的情况下完成原地修改第四你的代码对极端输入有没有防御性。单链表反转是一个几乎人人听过答案的题但“听过答案”和“能无bug地写出来”之间隔着一条鸿沟。我见过不少候选人一上来就说“用栈”或者在循环里用头插法重建链表。这些做法在功能上能跑通但如果面试官追问一句“空间复杂度是多少”很多人就卡住了。机试通常要求的是O(1)额外空间意味着必须在原链表上通过改动指针方向来完成反转。这个约束决定了你的思路必须围绕“指针翻转”展开而不是投机取巧。1.2 常见的错误姿势有个反直觉的现象越是简单的题错误越多样化。就反转链表而言我统计过候选人现场写代码时的典型错误排名靠前的是这么几类修改指针时把下一个节点弄丢了。常见于只用一个临时变量保存前驱没有保存当前节点的后继结果循环一推进就访问了野指针。while循环的条件写错最常见的错误是写成while (cur.next ! null)导致最后一个节点没有被处理。返回结果错误忘记返回新的头节点即原来的尾节点而是返回了移动后的cur或者prev整个结果变成了一串残缺的节点。递归版本没有处理好递归返回后的“连接”问题把原头节点的next置空放在了错误的位置导致链表成环。这些错误都不是智力问题而是对链表结构不敏感。链表和数组最大的不同在于数组删一个元素后面的元素自动补齐链表删一个节点全靠你手动把前后两个邻居接上一步没接对整条链就断了。反转链表就是把“手动接邻居”这个动作练到极致。我在带新人的时候常打一个比方链表就像一排手拉手的人反转链表不是让这些人整体乾坤大挪移而是让每个人都转过身去牵住原来身后的那个人。听起来很简单难点在于“转身”的瞬间你得保证每个人都还是连着点什么东西不至于有人撒手消失。2. 迭代反转三指针游走的本质拆解迭代法是反转链表最经典也最实用的解法绝大多数机试答案都基于它。整个算法的核心就是维护三个指针prev前驱、cur当前节点、next后继的缓存。每次迭代做两件事缓存后继翻转箭头。2.1 为什么需要三个指针这里我先解释一个新手最容易困惑的点明明要改当前节点cur.next的指向为什么非得先缓存next因为这个操作一旦执行cur和原来的后继之间就断开了。如果不先把它存到临时变量里循环的下一步就不知道怎么走到链表的下一个位置。可以这样理解你正在一个队伍里挨个给人“转身”每次给一个人转身前你先拉住他身后那个人的手免得他转身之后弄丢后边那个人。等这个人转好了你走过去拉住下一个人再重复。这个“先拉住身后的人”的动作就是next cur.next。整个迭代过程如下ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; ListNode* cur head; while (cur ! nullptr) { ListNode* next cur-next; // 1.记住下一个位置 cur-next prev; // 2.指针翻转 prev cur; // 3.prev前进 cur next; // 4.cur前进 } return prev; }这段代码有几个细节值得玩味。初始状态prev nullptr是刻意为之。原链表的头节点反转后应该变成尾节点而尾节点的next必须是空指针所以第一个遍历到的节点它的next需要指向nullptr。这个初始值设置是整段代码的精髓。当循环结束时cur已经走到链表的尾部之外也就是nullptr而prev恰好停留在原链表的最后一个节点上也就是新链表的头节点。所以返回值是prev不是cur也不是head。这个细节写错过一次之后基本就不会再忘了。2.2 边界条件测试的三板斧代码写完之后很多人直接交卷结果栽在测试用例上。我自己的习惯是永远跑三个用例空链表、单节点链表、多节点链表。空链表就是head nullptr这时候循环压根不会进去直接返回prev也就是nullptr符合预期。单节点链表cur指向唯一节点next为空翻转后cur-next nullptrprev变成这个节点返回它也正确。三节点以上的常规情况就不用多说了。真正容易忽略的是链表长度为2的情形。两个节点的时候很多人会手误写成while (cur-next ! nullptr)然后处理完第一个节点就停了返回的prev指向原来的第一个节点但它后面还连着原来的第二个节点。从输出看链表似乎“反转了一半”如果面试官不仔细看还可能被蒙混过去但大概率会被追问。2.3 迭代法的时间与空间复杂度迭代法的时间复杂度是O(n)空间复杂度是O(1)。这里的空间复杂度指的是额外空间——除了几个指针变量外没有使用与链表长度相关的存储。很多候选人会把函数栈帧、返回地址之类的也算进去其实不必那么教条。机试中讨论复杂度时默认指的是算法额外开辟的空间不影响输入数据本身。你要向面试官证明的不仅是“我能写出来”还要能说明白“为什么空间复杂度是O(1)”。因为哪怕你用了一个长度为n的数组把节点地址存下来然后倒序重连功能也对但额外空间就变成O(n)了。机试的隐性要求往往是“写出最优解”如果你一上来就给一个O(n)空间的做法即使功能正确也很难拿到满分。从另一个角度看迭代法的思路其实可以推广到很多链表操作凡是涉及“调整相邻节点关系”的问题几乎都可以用“缓存后继、翻转指针、同步前进”这个模式解决。比如后面要讲的区间反转和K个一组反转底层都是这一套东西。3. 递归反转让函数调用栈帮你干活迭代法直观但扛不住面试官追问“你还能用别的方式实现吗”。这时候递归版就该登场了。递归反转的代码通常更短看起来也更优雅但理解难度反而更高因为它的执行过程是“从后往前”的不符合人类从左到右的直觉。3.1 递归反转的核心思维递归反转链表可以这样定义先反转当前节点后面的整条子链得到一个“后半段的新链表头”然后把这个新链表的尾节点指向当前节点最后把当前节点的next置为空返回新链表头。这里最绕的地方在于你怎么知道反转后的“尾节点”是谁其实你不需要显式地用一个指针去记录它因为原链表当前节点head的下一个节点在子链表反转完成后会变成子链表反转结果中的最后一个节点。听起来像一个绕口令我拆开说。假设链表是1 - 2 - 3 - 4 - null现在对2 - 3 - 4这一段递归反转得到的新链表是4 - 3 - 2 - null。那么让head-next也就是节点2执行head-next-next head就等于在2的后面接上1。这句话是递归版的灵魂很多人就是卡在这里。我见过一个非常形象的比喻递归反转就像一群人站成一排每个人喊身后的人转过身去但是“转过身去”这个动作是由最末尾的人先开始一直传到最前面。最后一个人转过身来面对的是空倒数第二个人转过身来面对的是最后那个人一直传到第一个人整个队伍就反过来了。递归版代码实现如下ListNode* reverseListRecursive(ListNode* head) { if (head nullptr || head-next nullptr) { return head; } ListNode* newHead reverseListRecursive(head-next); head-next-next head; head-next nullptr; return newHead; }这段代码只有短短几行但执行过程非常微妙。递归的终止条件是head nullptr || head-next nullptr前者处理空链表后者处理单节点链表和递归链的最后一层。注意这里不能只写head-next nullptr否则空链表会直接段错误。3.2 递归执行过程的拆解以一个四节点链表1 - 2 - 3 - 4 - null为例逐步演算调用reverse(1)不满足终止条件调用reverse(2)。reverse(2)调用reverse(3)reverse(3)调用reverse(4)。reverse(4)满足head-next nullptr直接返回节点4。此时递归开始回溯。回到reverse(3)这一层head是节点3head-next是节点4。执行head-next-next head也就是4-next 3再执行head-next nullptr也就是3-next nullptr。此时子链变成4 - 3 - null返回节点4作为newHead。回到reverse(2)这一层head是节点2head-next是节点3。执行3-next 2再执行2-next nullptr。子链变成4 - 3 - 2 - null。回到reverse(1)这一层执行2-next 1再执行1-next nullptr。整条链表变成4 - 3 - 2 - 1 - null返回newHead即节点4。注意第4步里有一个关键点head-next-next head的时候需要用head-next这个指针找到原来的后继此时这个后继在递归返回后已经是子链的尾节点。如果你在原链表里就用一个变量保存了head-next效果也一样但代码里直接链式访问更简洁。前提是你理解这一步是在递归返回后执行的此时head-next指向的节点在子链中的位置是最后一位。很多人问我为什么递归反转的最后一定要把head-next nullptr原因很简单原链表的头节点在反转后变成了尾节点尾节点的next必须是空。如果漏掉这一句链表里就会留下一个环。比如上面的例子如果不把1-next置空最终链表就是4 - 3 - 2 - 1 - 2 - 3 - 4 - ...直接死循环。3.3 递归的空间复杂度与面试表现递归反转的时间复杂度同样是O(n)但空间复杂度是O(n)因为递归调用栈最深会压到n层。这一点和迭代法相比是劣势。不过面试官问递归通常不是真的指望你用O(1)空间而是考察两点一是你是否理解递归的分解逻辑二是你是否能准确说出代价。我在实际面试中看到很多人把递归版的代码背得很熟但被问到“递归最大递归深度是多少”时懵了。链表长度为n递归深度就是n超过一万节点很容易栈溢出。所以在机试时如果题目没有特别说明我一般建议默认写迭代法如果面试官主动问“有没有递归解法”你再优雅地抛出这段代码并主动说明空间复杂度的区别反而能成为加分项。另一个常见的追问是“递归反转能不能改造成尾递归”。这里可以给一个比较专业的回答这个版本不是尾递归因为递归返回后还有head-next-next head这个额外操作。真正的尾递归需要把累积状态作为参数传下去但链表的反转需要从后往前建立连接严格意义上的尾递归并不容易实现通常得借助传入prev指针的技巧。如果你被追问到这个程度直接把下面这个“伪尾递归”写法抛出来效果会很好ListNode* reverseHelper(ListNode* node, ListNode* prev) { if (node nullptr) return prev; ListNode* next node-next; node-next prev; return reverseHelper(next, node); } ListNode* reverseList(ListNode* head) { return reverseHelper(head, nullptr); }实际上这已经是迭代法的递归写法压栈深度仍为n但表达形式更接近尾递归。编译器不一定能优化它但这个思路能展现出你对递归本质的理解比单纯背代码强得多。4. 机试真正爱考的反转链表变体全攻略如果只考原题“反转整个链表”那这题早就被刷穿题库了。现实情况是面试官会在原题的基础上不断加码最常见的变体包括反转链表的前N个节点、反转指定区间内的节点、K个一组反转链表、链表两两交换节点。这些都是同一个“指针翻转”思想的不同应用场景。4.1 反转前N个节点一个需要“后门”的改动反转前N个节点意思是只把链表开头的前N个节点翻转后面的节点保持原顺序。例如1 - 2 - 3 - 4 - 5翻转前3个得到3 - 2 - 1 - 4 - 5。这个问题是理解区间反转的跳板也是K个一组反转的前置技巧。如果套用整个链表反转的思路会发现一个关键差异整个链表反转时原来头节点翻转后作为新链表的尾节点它的next要置空。但反转前N个节点时经过翻转的尾节点原来的头节点反而要连接上第N1个节点。这个“连接后继”的动作就是所谓的“后门”。代码实现时需要一个类似successor的变量来记录第N1个节点ListNode* successor nullptr; ListNode* reverseN(ListNode* head, int n) { if (n 1) { successor head-next; return head; } ListNode* newHead reverseN(head-next, n - 1); head-next-next head; head-next successor; return newHead; }这版代码里n 1时当前节点就是需要反转的最后一个节点它的后继就是整个反转段的后门必须记录下来。在返回的路上每一层都把head-next指向这个successor。这样做的效果是原本的头部节点最终连接到第N1个节点上而中间节点仍然按照反转逻辑互相翻转。如果你没接触过这个写法可能会觉得successor为什么始终不变因为第N1个节点在整个反转过程中位置固定递归的每一层都只需要记住它不随着递归深度而改变。4.2 区间反转LeetCode 92的完整解法区间反转比前N个更进一层反转从第m个节点到第n个节点其余部分保持不变。例如1 - 2 - 3 - 4 - 5m2n4结果是1 - 4 - 3 - 2 - 5。处理这个问题有两种主流思路。一种是“定位法”先找到第m-1个节点称为leftPrev把从第m个节点开始的子链反转反转长度为n-m1然后接回原来的链表。这要求你用一个专门的反转函数。另一种是“迭代头插法”在从m到n的遍历过程中不断把当前节点摘下并插入到leftPrev后面实现局部反转。我比较推荐思维上更直观的“定位法”因为它的每一步都和基础思路挂钩。先写一个反转链表区间前len个节点的函数可以直接利用上面的reverseN但要注意reverseN是在反转前n个节点时会把尾部接回successor而区间反转还需要把左边界之前的节点和新区间头部接上。写成迭代版更不容易出错ListNode* reverseBetween(ListNode* head, int m, int n) { if (head nullptr || m n) return head; ListNode* dummy new ListNode(0); dummy-next head; ListNode* pre dummy; for (int i 1; i m; i) { pre pre-next; } ListNode* cur pre-next; ListNode* next nullptr; for (int i m; i n; i) { next cur-next; cur-next next-next; next-next pre-next; pre-next next; } return dummy-next; }这种头插法的精妙之处在于它不需要显式地记录反转后的尾节点而是把每一个新遇见节点都插到区间头部之前也就是pre的后面。循环次数是n - m次每次处理一个节点。变量语义必须盯牢cur始终指向当前区间的第一个未处理节点它的位置在循环中不断后移next是待插入的节点pre-next每次更新为最新插入的节点。我把这个过程的循环变量跟踪列一下方便理解。初始链表1 - 2 - 3 - 4 - 5m2n4。开始前pre指向节点1cur指向节点2。第一轮循环next指向节点3执行cur-next next-next即2-next 4然后next-next pre-next即3-next 2再pre-next next即1-next 3。链表变成1 - 3 - 2 - 4 - 5。第二轮next指向节点42-next 54-next 31-next 4。最终得到1 - 4 - 3 - 2 - 5。这个过程非常清晰也特别适合在面试时边画边讲。4.3 K个一组反转链表合成题的考场表现K个一组反转是LeetCode第25题它的描述是每K个节点一组组内分别反转如果剩余节点不足K个保持原样。例如1 - 2 - 3 - 4 - 5 - 6 - 7K3最终变成3 - 2 - 1 - 6 - 5 - 4 - 7。这道题是典型的“能者上瘾、弱者劝退”的类型。但其实它的结构极其清晰先数出K个节点反转这K个节点然后递归处理链表剩余部分。递归在这里非常适合因为每一组的反转逻辑完全相同而且组与组之间的连接关系有固定模式。核心代码长这样ListNode* reverseKGroup(ListNode* head, int k) { if (head nullptr) return nullptr; ListNode* end head; for (int i 0; i k; i) { if (end nullptr) return head; end end-next; } ListNode* newHead reverse(head, end); head-next reverseKGroup(end, k); return newHead; } ListNode* reverse(ListNode* start, ListNode* end) { ListNode* prev nullptr; ListNode* cur start; while (cur ! end) { ListNode* next cur-next; cur-next prev; prev cur; cur next; } return prev; }这里的关键是end的定义。end不是“第K个节点”而是“第K个节点的下一个节点”。这样设计的目的是让reverse函数可以方便地以end作为终止条件。反转结束后整个K个节点的组被翻转而原本的start节点变成了组内的尾节点它应该连接上下一组的头节点。因此head-next reverseKGroup(end, k)这一步特别重要。我看过不少人死记硬背这个解法但一换参数就乱了。建议你亲自在草稿纸上画出递归树。以1 - 2 - 3 - 4 - 5K2为例第一轮end指向节点3反转1 - 2得到2 - 1然后1-next reverseKGroup(3,2)递归处理3 - 4 - 5再反转3 - 4得到4 - 33-next递归处理5因为剩余不足2个直接返回5。最终结果是2 - 1 - 4 - 3 - 5。4.4 两两交换节点K2的特例如果K2K个一组反转就退化成“两两交换节点”也就是LeetCode第24题。不过这题有一个更简单的迭代解法思路很像是区间反转的头插法但没有区间限制。代码可以这样写ListNode* swapPairs(ListNode* head) { ListNode* dummy new ListNode(0); dummy-next head; ListNode* pre dummy; while (pre-next ! nullptr pre-next-next ! nullptr) { ListNode* first pre-next; ListNode* second first-next; first-next second-next; second-next first; pre-next second; pre first; } return dummy-next; }这个写法里pre永远指向交换段的前一个节点。每次交换两个节点后pre移动到原first节点的位置因为现在这个位置是下一对待处理节点的前驱。用dummy节点可以避免对头节点单独做特殊判断这个技巧在链表的增删改查里非常常用。遇到链表长度是奇数时最后一对不够两个节点循环条件中的pre-next-next ! nullptr就失效了跳出循环后最后一个节点保留原样。这个边界行为和K个一组反转的“不足K不反转”保持一致。5. 现场写码时的实战经验与避坑清单很多人觉得自己刷题时写得挺好一到机试就发挥失常。我观察下来除了紧张因素外更重要的是机试环境ACM模式或核心代码模式和本地刷题环境之间的差异。ACM模式下需要自己处理输入输出、构建链表这比在LeetCode上直接提交函数多了一个步骤核心代码模式相对友好但你仍然要自己定义ListNode结构体。5.1 链表结构体定义与手写注意事项机试时如果题目没有给链表结构体你需要自己写。C常见定义是struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} };如果是ACM模式你还需要根据输入数组手动构造链表并用循环输出结果。这中间最容易出错的就是节点内存管理虽然机试一般不管内存泄漏但如果你在本地用new创建节点测试完不释放检查器不会报错但同学问起来就有点尴尬了。我给一个构造链表的模板ListNode* buildList(const vectorint nums) { ListNode* dummy new ListNode(0); ListNode* cur dummy; for (int num : nums) { cur-next new ListNode(num); cur cur-next; } return dummy-next; } void printList(ListNode* head) { while (head ! nullptr) { cout head-val; if (head-next ! nullptr) cout - ; head head-next; } cout endl; }输出链表时注意不要真的修改head因为打印函数结束后你还需要原来的头节点。上面的实现用了局部变量head直接移动它没问题因为它是值拷贝不影响外部变量。5.2 测试用例设计的套路机试提交前我强烈建议你在脑子里跑一遍这些用例空链表[]输出应该是空。单节点[1]输出[1]。双节点[1,2]输出[2,1]。三个节点[1,2,3]输出[3,2,1]。带重复元素[1,1,2]输出[2,1,1]。负数和零[-1,0,3]输出[3,0,-1]。边界条件一旦站稳代码的正确性基本就有保障了。如果你用的是递归实现建议额外测一个长链比如[1,2,...,10]防止递归深度过深时系统栈溢出。虽然节点数少没什么事但如果你用了递归版本又有可能被面试官追问时就可以用这个用例来说明递归的局限。5.3 几个隐蔽的坑我还想单独提三个容易忽视的点。第一如果链表中有环那么反转会陷入死循环。但机试一般不会出环状链表的反转因为链表定义没有特殊说明时默认无环。第二反转函数千万不要在循环外把head-next置空除非你确定head是最后一个节点。第三使用dummy节点时记得return的是dummy-next而不是dummy本身。每一次看到有人在这几个地方翻车我都替他们惋惜。核心代码模式中你只需要实现一个函数不需要处理输入输出这是一个隐藏的便利但同时也意味着测试时你要自己构造链表。我平时刷题时习惯把链表构造和控制台打印写成工具函数每次做链表题直接复用省了很多时间。这个习惯值得你刻意培养因为机试时间紧张每省一分钟都意味着多一分余裕去思考难题。还有一个小建议在提交前把代码里所有变量名读一遍确认没有next和head混用。链表题的大部分bug都是变量名太像导致的。列出这个清单不是多此一举许多“身经百战”的选手都会在最后扫一眼这些关键点。6. 写在最后反转链表到底在考什么说回最开始的问题。反转链表被机试反复考察因为它是一个完美的“压力测试点”。它不难到让人绝望但难到足以暴露一个选手对链表底层结构的熟悉程度。一个人是背会了解法还是真正理解了指针的翻转逻辑往往几句话就能问出来。如果让我给准备机试的人一个建议我会说不要只满足于“会写迭代版”也不要只停留在“看得懂递归版”。你要做到的是——闭上眼睛在脑海里让一个三指针小车缓缓开过链表明确每一步之后prev、cur、next各指向哪个节点再让递归栈一层层展开又回归看清每一层的head如何翻转、如何断链、如何接上。当你能用自己的话把这两条路都讲明白反转链表这个钉子户才算真正被你拿下了。我在实际带队面试时看到那些最终拿到高评价的候选人往往不是把代码写得最花哨的人而是能在写完代码后平静说出“这个解法额外空间是O(1)如果要确保空链表也安全我建议在开头加一个判空”的人。这种自信来源于对基础的掌控而不是对题海战术的依赖。如果你在机试中也遇到了反转链表希望这篇文章能帮你把这几分钟变成整场考试的定心丸。