1. 反转链表到底在反转什么链表反转是LeetCode上出镜率最高的题目之一没有之一。我刷了这么多题面试里被问到的链表题十道里有六道跟反转沾边——要么是完整反转要么是反转前K个要么是两两交换要么是区间反转。所以把这个基础款吃透后面那些变种就是在这个骨架上加参数而已。先把问题说清楚。给你一个单链表的头节点比如1 - 2 - 3 - 4 - 5 - NULL要求你把它变成5 - 4 - 3 - 2 - 1 - NULL。看起来简单但真正动手写的时候很多人会在指针操作上翻车。为什么因为单链表只能单向遍历你把当前节点的next指向前一个节点之后就找不到后面的节点了。所以核心难点就一个在改变指针方向之前先把后面的路记下来。这篇文章适合谁看如果你刚开始刷LeetCode对指针操作还不太有手感那这篇就是写给你的。如果你已经刷过一些题但每次写反转链表都要想半天那这篇也能帮你把思路固化下来。我会用C语言来写因为C的指针操作最赤裸没有语法糖帮你兜底把C写明白了其他语言就是换个写法的事。2. 解题思路的拆解与方案选型2.1 为什么迭代法是最优先的选择反转链表的解法主要有两种迭代和递归。我先说结论——面试里优先写迭代法。原因不复杂迭代法空间复杂度是O(1)递归法虽然代码短但空间复杂度是O(n)因为每一层递归都要压栈。而且递归法在链表特别长的时候有栈溢出的风险虽然LeetCode的测试用例一般不会长到那个程度但面试官如果追问“有没有更优的空间方案”你递归写到一半就尴尬了。迭代法的核心思想用一句话概括用三个指针一边遍历一边掉头。这三个指针分别是prev指向前一个节点初始为NULLcurr指向当前节点初始为headnext临时存储下一个节点防止断链你可以把整个过程想象成一群人排队原本每个人都面朝前方现在要求所有人转身面朝后方。你不能让一个人直接转因为他转过去之后他前面那个人就找不到后面的人了。所以你需要一个人一个人地处理每处理一个人之前先记住他后面是谁。2.2 递归法的适用场景与局限递归法不是不能用但你要清楚它的适用边界。递归的思路是从最后一个节点开始反转然后逐层往回走。代码确实简洁但有几个实际问题第一当链表长度超过几万的时候递归深度就危险了。第二递归法的思路在面试中解释起来反而更绕面试官如果让你画图说明迭代法画起来更直观。第三很多变种题比如反转区间、K个一组反转用迭代法更容易控制边界条件。所以我的建议是先把迭代法练到闭着眼睛都能写对递归法作为知识储备了解即可。面试的时候主动写迭代如果面试官问“还有别的方法吗”你再把递归思路讲出来这样节奏就很舒服。2.3 三个指针的初始状态为什么这样设很多人会问为什么prev要初始化为NULL因为反转之后原来的头节点会变成尾节点而尾节点的next必须是NULL。你初始把prev设为NULL第一次循环的时候curr-next prev就自然把第一个节点的next置为NULL了不需要额外处理尾节点。那curr初始为head这个没什么好说的从头开始遍历。关键是next指针它必须在每次改变curr-next之前就保存好curr-next的原始值。顺序不能乱next curr-next; // 先记住后面的路 curr-next prev; // 再掉头 prev curr; // prev往前挪 curr next; // curr往前挪这四行的顺序是铁律任何一行提前或延后都会导致断链或者死循环。我见过有人把curr-next prev写在第一行结果next拿到的已经是修改后的值了整个链表直接断掉。3. 完整代码实现与逐行解析3.1 迭代法完整实现先给出结构体定义这是LeetCode的标准定义struct ListNode { int val; struct ListNode *next; };然后是反转函数struct ListNode* reverseList(struct ListNode* head) { struct ListNode *prev NULL; struct ListNode *curr head; struct ListNode *next NULL; while (curr ! NULL) { next curr-next; curr-next prev; prev curr; curr next; } return prev; }就这十几行但每一行都有讲究。我来逐行拆解。prev NULL前面说过了为了处理尾节点。curr head从头开始。next NULL初始化而已进循环后第一件事就是给它赋值。循环条件是curr ! NULL不是curr-next ! NULL。为什么因为你要处理每一个节点包括最后一个节点。如果用curr-next ! NULL作为条件最后一个节点就不会被处理它的next还指向倒数第二个节点结果就是尾节点没有正确置NULL。循环体内四行代码的顺序前面已经强调过了。循环结束后curr已经是NULL了prev指向的是原来的最后一个节点也就是反转后的头节点。所以返回prev。3.2 手动模拟执行过程光看代码可能还不够直观我带你走一遍1 - 2 - 3 - NULL这个例子。初始状态prev NULLcurr 1next NULL。第一轮循环next curr-next所以next 2curr-next prev所以1-next NULLprev curr所以prev 1curr next所以curr 2此时链表状态1 - NULLprev指向1curr指向2。第二轮循环next curr-next所以next 3curr-next prev所以2-next 1prev curr所以prev 2curr next所以curr 3此时链表状态2 - 1 - NULLprev指向2curr指向3。第三轮循环next curr-next所以next NULLcurr-next prev所以3-next 2prev curr所以prev 3curr next所以curr NULL此时链表状态3 - 2 - 1 - NULLprev指向3curr为NULL。循环条件不满足退出。返回prev也就是节点3反转完成。注意手动模拟看起来简单但真正写代码的时候很多人会在prev和curr的移动顺序上犯错。记住一个原则——先保存再掉头最后移动。3.3 递归法实现与对比递归法的代码是这样的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; }递归的终止条件是链表为空或者只有一个节点直接返回。否则先递归处理后面的部分得到反转后的新头节点newHead。然后关键的两行head-next-next head让后一个节点指回当前节点head-next NULL断开当前节点原来的指向。这两行的顺序也不能反。如果先执行head-next NULL那head-next-next就找不到原来的后一个节点了。递归法的空间复杂度是O(n)因为递归调用栈的深度等于链表长度。迭代法是O(1)。时间复杂度两者都是O(n)每个节点处理一次。对比维度迭代法递归法时间复杂度O(n)O(n)空间复杂度O(1)O(n)代码长度稍长更短栈溢出风险无链表过长时有面试推荐度优先备选4. 实操中容易踩的坑与排查方法4.1 指针操作顺序错误导致断链这是最常见的错误没有之一。我刚开始写的时候也犯过把curr-next prev写在next curr-next前面结果next拿到的是已经被修改的值链表从中间断开后面的节点全部丢失。排查方法很简单在纸上画三个格子代表三个指针每执行一行就更新一次格子的指向画完一轮循环你就知道哪里错了。不要偷懒在脑子里模拟链表操作必须画图。4.2 循环条件写错导致尾节点未处理有人把while (curr ! NULL)写成while (curr-next ! NULL)结果最后一个节点没有被反转它的next还指向倒数第二个节点形成环或者尾节点没有正确置NULL。这个错误的排查方法是用两个节点的链表测试。1 - 2 - NULL如果反转后变成2 - 1 - 2 - ...这种环那就是循环条件写错了。4.3 返回值写错循环结束后应该返回prev不是curr也不是head。因为curr已经是NULL了head现在是尾节点。返回prev才是反转后的新头节点。这个错误比较隐蔽因为如果你在LeetCode上提交返回错误的节点会导致输出完全不对但代码逻辑看起来没问题。记住一个口诀循环结束prev是新头。4.4 空链表和单节点链表的边界处理空链表head NULL的情况迭代法里curr head NULL循环条件不满足直接返回prev NULL正确。单节点链表1 - NULL循环执行一次prev变成1curr变成NULL返回1也正确。所以迭代法天然处理了这两种边界情况不需要额外加if判断。但递归法必须加head NULL || head-next NULL的判断否则会空指针解引用。提示写完代码后至少用三种情况测试——空链表、单节点、三节点以上的正常链表。这三种覆盖了所有边界。4.5 常见问题速查表问题现象可能原因排查方法输出只有第一个节点next保存时机错误检查四行代码顺序输出形成环循环条件写错用两节点链表测试输出顺序不对返回值写错确认返回的是prev程序崩溃空指针解引用检查递归终止条件尾节点next不为NULL循环少执行一次检查while条件5. 从反转链表延伸出去的变种题5.1 反转前K个节点这是反转链表的直接变种。思路是先找到第K个节点记录它的next然后把前K个节点当成一个独立的链表反转最后把反转后的尾节点接上之前记录的next。关键点在于反转之前要先保存第K1个节点的位置否则反转之后你就找不到后面了。这个变种题在面试中出现频率很高因为它同时考察了链表遍历、反转和边界处理。5.2 K个一组反转链表这是上一题的升级版要求每K个节点一组进行反转最后不足K个的保持原样。思路是先用一个指针走K步如果走不满K步就直接返回如果走满了就反转这K个节点然后递归或迭代处理后面的部分。这道题的难点在于组与组之间的衔接。反转完一组之后原来的头节点变成了尾节点它需要指向下一组反转后的新头节点。所以你需要额外记录上一组的尾节点。5.3 反转指定区间给你一个链表和两个整数left和right要求反转从位置left到位置right的节点。这道题需要你先走到left位置的前一个节点然后对left到right这一段执行反转最后把前后接起来。这道题最容易出错的地方是left等于1的情况也就是从头节点开始反转。这时候你没有“前一个节点”需要用一个哑节点dummy node来简化处理。哑节点是链表题里的万能技巧很多边界问题加一个哑节点就迎刃而解。5.4 两两交换链表中的节点这是K等于2的特殊情况。可以用迭代法也可以用递归法。迭代法的思路是每次处理两个节点交换它们的指向然后移动到下一对。递归法的思路更简洁但空间复杂度是O(n)。这道题在面试中经常作为反转链表的follow-up出现面试官想看看你能不能把学到的指针操作迁移到新场景。6. 我刷这道题的一些个人体会反转链表这道题我前前后后刷了不下十遍。不是因为我笨而是因为每次隔一段时间不写指针操作的细节就会模糊。后来我总结了一个方法不要背代码背口诀。口诀就是八个字先存后改先移后判。“先存后改”说的是在改变curr-next之前必须先保存curr-next的原始值。“先移后判”说的是在判断循环条件之前必须先移动指针。这八个字覆盖了迭代法最容易出错的两个点。另外我强烈建议你在纸上画图。链表题不像数组题数组题你在脑子里过一遍就行链表题必须画图。我见过太多人在面试的时候代码写得飞快但面试官让他画图解释的时候就开始卡壳。画图不仅能帮你理清思路还能让面试官看到你的思考过程。还有一点C语言写链表题的时候struct ListNode *这个类型名太长了写起来很烦。我一般会在函数开头用typedef简化一下或者直接用ListNode *如果题目已经typedef过了。但要注意LeetCode的C语言环境里结构体定义是固定的你不能改所以只能在函数内部用局部变量的时候尽量简洁。最后说一个心态问题。反转链表是链表题的基础但基础不代表简单。很多人觉得这道题太简单了刷一遍就过了结果面试的时候被问到变种题就懵了。我的建议是把反转链表当成一个模板来练练到你能在五分钟内写出无bug的迭代版本然后再去刷变种题。这样你的链表题正确率会有质的提升。后续如果你想把链表这块彻底吃透我建议按这个顺序刷反转链表 - 反转前K个 - K个一组反转 - 反转区间 - 两两交换 - 重排链表 - 合并两个有序链表 - 合并K个有序链表。这一套下来链表的基本操作你就全覆盖了。