1. 从问题本质说起反转链表到底在反转什么1.1 单链表的数据结构与反转的数学定义单链表反转可能是数据结构面试里出现频率最高的一道题没有之一。很多初学者拿到这道题的第一反应是“把链表倒过来输出”于是先遍历一遍存到数组再反向打印这显然是错了。反转链表不是“倒着读”而是“倒着连”——你要真正改变每个节点的next指针方向让原本指向下一个节点的指针指向前一个节点最后让头指针指向原来的尾节点。理解这一点前得先把单链表的结构刻在脑子里。一个单链表的节点通常只有两个部分data数据域和next指针域。next存的是下一个节点的地址最后一个节点的next是null。比如有三个节点A-B-CA.nextBB.nextCC.nextnull。反转之后应该是C-B-A也就是A.nextnullB.nextAC.nextB而链表头从A变成了C。这里有个关键认知在单链表里你没有办法通过某个节点找到它的前驱因为每个节点只记录了后继的地址。所以反转的本质是“一场指针方向的大规模改造”你必须在遍历的过程中同时处理好当前节点、前一个节点、下一个节点三者之间的关系。缺少任何一环不是断链就是死循环。1.2 为什么这道题能长青不衰你翻任何一份算法题清单基本都会看到单链表反转。它考查的东西太精准了第一考查你是否理解指针和引用的本质是不是只会用数组思维思考问题第二考查你的边界意识空链表、只有一个节点、两个节点、长链表这些情况是否都能正确处理第三考查你的代码基本功会不会在改指针时把中间状态搞丢。在工程场景里反转链表的应用同样不少。比如说LRU缓存淘汰算法里链表的节点被访问后需要移动到链表头部本质就是“摘除头插”操作这和反转链表用的是同一套指针控制手法。再比如浏览器前进后退的历史记录用双链表实现时需要在两个指针方向间切换思路也同源。如果你写过自平衡二叉树的旋转操作会发现“旋转”本质上也是在重新组织节点间的父子关系和链表反转在“重新指路”这个层面殊途同归。换个角度说反转链表是一把“钥匙”。它会了你后面接触“K个一组反转”“反转区间链表”“回文链表判断”“链表两数相加”这些题时会有一种“哦原来都是同一套东西”的顿悟感。所以不管是为了面试还是为了真正理解数据结构这一关必须过。1.3 几个绕不开的典型场景我把反转链表这个题目拆成几个实际场景来说明你会发现每一个场景都对操作有不同要求。第一个场景是纯手写算法题比如LeetCode 206。题目要求只用O(1)额外空间也就是你不能再开一个新链表去装必须在原链表上完成反转。这就逼着你用迭代或递归的原地反转方案而不是图省事用栈。第二个场景是帮别人答疑或者做辅导。你会看到很多新手在反转链表时喜欢创建一个新链表然后把旧链表头插进新链表。这当然也能得到反转结果但空间复杂度变成了O(n)而且节点全都重新new了一遍原链表的空间被浪费了。要讲清楚“为什么推荐原地反转”就得从链表结构本身入手。第三个场景是实验课或作业比如有些学校的数据结构实验会要求“实现单链表的基本操作包含反转”。这时候你需要写的可能是完整的可运行代码包含节点定义、链表构建、输出打印。这个场景下很多人会遇到“头节点要不要带头”的问题。有头节点的链表带头结点和没有头节点的链表不带头结点反转写法是有细微差别的下面我会专门展开。第四个场景是工程中的局部反转。比如一个链表很长你只需要翻转其中一段区间。这种需求在底层库、算法题变形中经常出现它考验的是你对“断链点”的精确定位能力。可以说把基础反转吃透后面这些变形都是小菜。2. 核心解法拆解迭代、递归、头插法与辅助栈2.1 迭代法三指针反转原理与手把手推导迭代法是反转链表最主流、最推荐掌握的方案时间复杂度O(n)空间复杂度O(1)。它的核心思想用一句话总结三个指针沿着链表走一遍边走边把next掉头。具体需要三个指针prev当前节点前面的那个节点初始为null因为新链表的尾节点要指向nullcurr当前正在处理的节点初始为原链表的头节点next当前节点的下一个节点用于防止指针反转后找不到后续链表每一步操作就是四步先用next保存curr.next然后把curr.next指向prev再让prev移动到curr的位置最后让curr移动到next的位置。等curr变成null时遍历结束prev恰好指向新链表的头。我用一个具体例子走一遍链表是1-2-3-null。初始状态prevnullcurr1nextnull。第一步next2保存后继curr.nextnull1指向null。此时链表被拆成1-null和2-3-null两段。prev1curr2。第二步next3curr.nextprev也就是2-1此时1-null2-1剩3。prev2curr3。第三步nextnullcurr.nextprev也就是3-2prev3currnull。循环结束返回prev也就是3。最终链表3-2-1-null反转完成。这里最核心的诀窍是永远先保存next再改curr.next。如果你先执行curr.next prev那么curr原来的后继就找不到了后面的整条链就丢了。这是新手最容易犯的错误也是我调试过无数次才总结出来的血泪经验。还有一个容易忽略的细节返回的节点是prev不是curr。循环结束时curr已经是null如果习惯性返回curr返回的就是空指针。所以很多题解会用newHead prev或者直接返回prev。2.2 递归法从后往前反转的核心思路递归法的代码写出来只有几行看起来优雅但理解起来比迭代法难一个量级。很多初学者盯着递归代码看很久都反应不过来它到底怎么完成反转的根本原因在于递归的“归”阶段在函数返回时反向执行“指针反转”就发生在这个阶段。递归的思路是假设当前节点为curr我们先递归反转curr.next这个子链表拿到反转后子链表的新头节点newHead。由于子链表反转完成后curr.next这个节点记为nextNode已经变成了子链表的尾节点我们只需要让nextNode.nextcurr再让curr.nextnull就完成了把curr接到子链表尾部这个操作。画个图会更清楚。假设链表是1-2-3-null。递归调用reverse(1)进入函数时1.next2。reverse(1)调用reverse(2)reverse(2)调用reverse(3)。reverse(3)发现3.next是null直接返回3作为newHead。回到reverse(2)这一层此时nextNode3。执行3.next22.nextnull。子链表变成3-2-null返回3。回到reverse(1)这一层此时nextNode2。执行2.next11.nextnull。此时子链表变成3-2-1-null返回3。看到关键点没有真正改变指针指向的操作发生在递归“归”回来的路上也就是每一层函数返回前。递归函数最深处是base case也就是链表为空或只有一个节点直接返回该节点。递归法虽然代码简洁但有两点必须注意。第一它空间复杂度是O(n)因为递归调用栈需要n层对于非常长的链表比如几百万个节点会直接栈溢出。第二要正确处理“新的头节点”也就是最深层返回的那个节点。很多人在递归内部把返回的newHead弄丢了导致最后返回的还是原头节点反转结果变成了“部分反转”。我在实战中通常建议递归法作为理解递归思想的学习工具真到面试或工程实现时优先写迭代法。除非面试官刻意要求“用递归实现”或者题目本身非常适合递归比如反转前k个节点否则没必要为了优雅去承担栈溢出的风险。2.3 头插法与辅助栈两种“绕路”方案除了上面两个经典解法还有两个思路值得一提它们不是在原链表上原地反转而是通过“新链表”或“辅助结构”完成反转。头插法思路也很好理解——遍历原链表把每个节点按顺序“头插”到新链表的头部。具体操作就是新建一个dummy节点作为新链表的头每次取原链表的节点p先把p.next保存下来然后把p插入到dummy和dummy.next之间。遍历结束后dummy.next就是反转后的新链表。头插法本质上是“生成新链表”它没有在原链表上修改指针所以空间复杂度O(n)。不过如果要求原地反转头插法并不符合要求但如果题目不限制额外空间它胜在逻辑简单、容易写对。辅助栈法更直观把链表所有节点依次压栈再依次弹出让弹出的节点逐个相连。由于栈是后进先出这个过程天然完成了反转。代码写起来很简单但空间复杂度同样是O(n)而且更“暴力”完全失去了链表的指针操作训练价值。我一般把它当成“从零开始理解反转”的教具而不会作为实际解法推荐。2.4 方法对比与选型建议我把上面几种核心方案放在一起做个对比方便你按场景选用。方案时间复杂度空间复杂度是否原地反转核心操作适用场景迭代法三指针O(n)O(1)是保存next、改向、移动指针面试首推、工程首选递归法O(n)O(n)是回溯时改向学习递归、链表较短时使用头插法新建链表O(n)O(n)否原链表节点头插到新链表允许额外空间、想快速写对辅助栈法O(n)O(n)否压栈、弹栈、重新连接只求可运行不追求复杂度从表中可以看出如果你的目标是用最优解完成反转迭代法几乎是唯一答案。递归法在面试中被问到的频率也很高但更多作为“考察递归理解”的题目出现。头插法和栈方法适合当做“思考辅助”或“保底写法”因为它们不容易出错但不满足O(1)空间要求。我个人的选型建议是先掌握迭代法把每一步的指针变化用笔画熟再掌握递归法理解“归”阶段修改next的精髓头插法和栈法了解即可。这样无论在面试中遇到哪种追问你都能接得住。3. 实操实现从0构建链表并完成反转Python C3.1 定义节点与构建链表反转链表不是单纯写一段函数就完事你还需要一个能跑起来的链表结构。这里我分别用Python和C演示包含了从节点定义、链表构建到反转、打印输出的完整闭环方便你在本地直接运行验证。先看Python版本class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def create_linked_list(arr): if not arr: return None head ListNode(arr[0]) curr head for num in arr[1:]: curr.next ListNode(num) curr curr.next return head def print_linked_list(head): nums [] while head: nums.append(str(head.val)) head head.next print( - .join(nums) - None)C版本类似#include iostream struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} }; ListNode* createLinkedList(const std::vectorint arr) { if (arr.empty()) return nullptr; ListNode* head new ListNode(arr[0]); ListNode* curr head; for (size_t i 1; i arr.size(); i) { curr-next new ListNode(arr[i]); curr curr-next; } return head; } void printLinkedList(ListNode* head) { while (head) { std::cout head-val - ; head head-next; } std::cout nullptr std::endl; }这里要补充一个基础知识点在Python中对象的赋值本质是“引用传递”你修改一个变量的next会作用到同一个对象上。很多新手在反转时容易把“变量”和“节点”搞混比如直接赋值curr nextNode这只会让局部变量指向另一个节点并没有修改链表结构。要修改链表必须修改节点的属性也就是curr.next prev让真正连接跳转。同理C里如果你用指针就要清楚指针本身和指针指向对象之间的区别。操作链表的本质是在操作“节点对象内部的next指针”而不是操作“指向节点的那个局部指针”。3.2 迭代法完整实现与逐行解释先上完整代码这段代码我是反复删改过的注释尽量保留了解释性def reverse_linked_list(head: ListNode) - ListNode: prev None curr head while curr: next_node curr.next # 1. 先保存下一个节点防止丢失 curr.next prev # 2. 掉头当前节点指向前一个节点 prev curr # 3. 前移prev curr next_node # 4. 前移curr return prev # 新头节点是prev逐步解释第一步prev初始化为None。这是反转后链表的尾节点应该指向的位置。注意不要初始化成head否则会产生循环后面会说。第二步进入while curr循环。循环条件不是cur ! None而是curr ! None直到curr为空才停止。第三步在循环体内部首先用next_node保存curr.next。这一步十分关键因为第三步就要覆盖curr.next的值了如果没提前保存原链表从curr的下一个位置开始就彻底脱离控制无法继续遍历。第四步修改curr.next指向prev。第一次循环时head节点会变成尾节点指向None后续循环中每个节点的next都会指向前一个节点。第五步同步前移prev和curr。prev变成currcurr变成next_node。注意顺序不能反如果你先移动currprev就找不到了。第六步循环结束后返回prev。此时prev就是原链表的尾节点也是新链表的头节点。C实现几乎同理ListNode* reverseLinkedList(ListNode* head) { ListNode* prev nullptr; ListNode* curr head; while (curr) { ListNode* nextNode curr-next; curr-next prev; prev curr; curr nextNode; } return prev; }不要小看这段代码它背后隐藏着一个非常经典的心法指针操作顺序永远遵循“先留后路再改方向最后挪位置”。这个心法不仅适用于反转还适用于链表插入、删除、交换等所有涉及指针变换的场景。3.3 递归法完整实现与逐行解释递归法同样先给代码def reverse_linked_list_recursive(head: ListNode) - ListNode: if not head or not head.next: return head new_head reverse_linked_list_recursive(head.next) head.next.next head head.next None return new_head逐行解释第一行如果是空链表或只有一个节点直接返回head。这就是递归的终止条件。第二行递归调用自己传入head.next。这行调用会一直走到链表的最后一个节点才停返回值是反转后的新表头。你可以把它理解为“先相信我身后的列表已经被别人反转好了并把新表头交给我”。第三行head.next.next head。这行代码是递归法的灵魂。head.next是原本的下一个节点在子链表反转完成后它已经变成子链表的尾节点所以head.next.next head本质是把当前节点接到子链表尾部的后面。换句话说上一层的nextNode也就是现在的尾节点的next指向了当前的head。第四行head.next None。因为原本head是指向下一个节点的现在head已经变成反转链表的尾节点了尾节点必须指向None否则链表里会出现环。第五行返回new_head。注意new_head在整个递归过程中只被赋值一次它一直是最深层返回的那个原尾节点。返回它才能保证整个反转后的链表头正确。C版本ListNode* reverseLinkedListRecursive(ListNode* head) { if (!head || !head-next) return head; ListNode* newHead reverseLinkedListRecursive(head-next); head-next-next head; head-next nullptr; return newHead; }这里要提醒一个容易混淆的点为什么head.next.next head不会造成死循环关键在于执行到这一行时head.next已经被上一层递归反转过了也就是说原来head.next指向的是下一个节点但子链表反转后head.next这个节点已经变成了子链表的尾节点它的next变成了null实际上由于上层递归的第四行已经把它置空。你在这个节点上接上head是引发了新一轮的“尾部对接”。整个递归执行完链表从原来的1-2-3-...-n变成了n-...-3-2-1。正因为每一层在处理完head后都把head.next置空才保证了不会出现环。从这个角度说递归法的逻辑可以总结成八个字先信任子问题再处理当前节点。你不需要在脑子里模拟完整递归过程只需要抓住“递归到最深处开始往回归回归时执行指针掉头”这一条主线。3.4 测试用例与边界验证不能只写实现不测试。我带你跑一遍完整测试代码确保各种边界情况都覆盖if __name__ __main__: # 用例1普通链表 arr [1, 2, 3, 4, 5] head create_linked_list(arr) print(原链表) print_linked_list(head) reversed_head reverse_linked_list(head) print(反转后) print_linked_list(reversed_head) # 用例2空链表 head None assert reverse_linked_list(head) is None # 用例3单节点链表 head ListNode(1) reversed_head reverse_linked_list(head) assert reversed_head.val 1 assert reversed_head.next is None # 用例4两个节点 head create_linked_list([1, 2]) reversed_head reverse_linked_list(head) print_linked_list(reversed_head) # 期望输出 2 - 1 - None我建议你在本地多测试几个特征用例逆序后的链表是否保持原来的节点对象而不是新创建的对象在Python里可以打印节点id来验证反转之后原链表头是否还指向原节点如果反转后原head.next已经变成None说明原地反转生效了。这些细节都能帮你确认自己真的理解了“反转”而不是“新建”。对于C版本记得在测试后使用delete释放节点内存避免内存泄漏。一个简单的做法是反转后重新遍历链表逐个释放。很多线上内存泄漏问题就出在“只管new不管delete”写算法题时不要求但工程实践里这是良好习惯。4. 常见坑点与排查技巧实录4.1 最容易踩的五个坑单链表反转的代码看似简单但很多人写的时候会反复踩坑。我结合自己踩过的和帮别人排查过的经验整理出五个典型问题。第一个坑没有保存next就改curr.next。这是最经典的新手错误。比如你直接写curr.next prev原链表从curr之后的整条链就找不到了。解决方法是严格按照“先保存next再改curr.next”的顺序。就算你自己觉得记住了也建议在代码里加一行next_node curr.next防止一紧张写错。第二个坑返回了错误的头节点。迭代法返回的是prev不是curr递归法返回的是newHead。很多面试者明明实现了反转却因为返回值写成了head导致整个链表看起来“没反转”或者“反转一半”。判断方法很简单返回前打印一下head.val和prev.val如果链表是1-2-3反转后head仍然指向1节点那一定返回错了。第三个坑循环条件写错。写成while curr.next导致最后一个节点没处理写成while curr导致进入循环但后面没有提前判空。正确的写法就是while curr让循环走到curr变成None为止。第四个坑递归没有正确设置终止条件。如果只写if not head不写if not head.next在处理单节点链表时确实也能返回但处理两个节点以上的链表时递归会在head.next为None时继续调用导致空指针异常。递归终止条件必须是if not head or not head.next。第五个坑对“带头结点”理解混乱。有的教材里链表带一个固定的头结点dummy head不存数据反转时这个头结点依然要存在而不能被当成普通节点一起反转。如果你是用“带头结点”的链表实验记住反转的目标实际上是头结点之后的“数据链表”反转完成后头结点的next要指向新的首节点。这里非常容易在实验中搞错导致打印结果怪异。4.2 调试技巧如何可视化链表反转过程链表调试比数组难因为链表的“形状”需要通过指针关系才能想象出来。我给你几个实用的可视化技巧。第一个技巧写一个打印函数输出带箭头和None的完整链条。我在前面已经给出了这个函数。不要用调试器去观察每个节点的内存地址那太反人类了。直接打印出val和next的跳转关系能一眼看出指针是否断掉。第二个技巧在循环内部临时打印中间状态。比如在迭代法的循环体末尾加一行print(fprev{prev.val if prev else None}, curr{curr.val if curr else None}, next{next_node.val if next_node else None})每次循环的print会显示三个指针的位置以及每个节点的next指向变化。用一个小链表比如[1,2,3]跑一下你就能直观地看到“指针是怎么一路滑过去的”。第三个技巧小数据演练。如果你DEBUG不出问题拿两个或三个节点在纸上画出来。很多人觉得画图浪费时间但链表题的核心就是“指针关系”画图是最可靠的定位手段。三个节点的反转过程中只要有一行代码顺序错了图一定能当场暴露问题。第四个技巧用assert做中途校验。例如每次循环结束时断言prev是curr的前驱next_node是curr的后继这样可以尽早发现问题代码段。4.3 扩展题目从反转链表走向更多变形单链表反转是一棵树的根很多高级题目都是在这个根上长出来的。我把它们整理成一份“变形清单”方便你按图索骥。第一类变形反转部分区间。题目要求反转链表从第m个节点到第n个节点之间的部分。做法是先找到第m个节点的前驱节点pre以及第n个节点以及它之后的节点然后对中间这段用迭代法反转最后把反转后的头尾接到原链表上。这里最关键的是要精确定位断点并且要保存好四个节点pre、start、end、endNext。第二类变形K个一组反转。也就是每K个节点反转一次如果剩余不足K个则保持不变。解法通常是递归先检查当前链表长度是否大于等于K然后反转前K个节点再用递归处理剩下的链表最后将两部分拼接。这里的难点是“保留每一组的头尾衔接”如果你基础反转不扎实这个题很容易绕晕。第三类变形回文链表判断。判断链表是否回文有一种经典做法是用快慢指针找到中点然后反转后半部分链表再逐节点比较。这里的反转就是普通反转但是要处理好“奇数长度和偶数长度时中点怎么定位”的问题。还有一道衍生题重排链表要求把一个链表L0-L1-...-Ln-1-Ln重排成L0-Ln-L1-Ln-1-...这种题同样大量使用“找中点反转后半段”的组合套路。第四类变形两数相加。给两个用链表表示的非负整数每个节点的值存储一位数字数字按照逆序存储要求返回一个链表表示两个数相加之和。解法本质是遍历两个链表同时做加法与进位反向链表的遍历顺序恰恰对应数字的从低位到高位所以不需要额外反转。但如果题目改成“正序存储”那么第一件事就要反转链表。我建议你把基础反转练熟后按这个清单一个个攻克每做完一道都会反过来加深对基础反转的理解。这也是我学习数据结构时走过的路先死磕核心题然后用变形题检验掌握程度。第四种场景也是很多人忽略的单链表反转在某些考试中会和“循环单链表”结合。比如你有一个循环单链表需要反转整个环。循环链表反转之后依然要保持循环也就是说反转前链表的尾节点指向头节点反转后原头节点变成尾节点它要指向原尾节点。这个问题常见的错误是反转后链表变成了普通链表导致环结构丢失。如果实验课上遇到“循环单链表反转”一定要记得额外处理尾节点和头节点的闭环。4.4 实验课与工程落地的额外提醒如果你是在数据结构实验课里做“单链表的基本操作实验”除了反转本身往往还要求你实现创建、插入、删除、查找、输出等基础操作然后在这基础上调用反转。这时候我建议你把“反转”函数设计得尽量独立它只需要接收一个头指针返回一个新的头指针不要依赖额外的全局变量。这样写出来的代码更符合模块化思维也方便自动化测试。在工程落地时还要考虑几个面试之外的细节。第一链表是否包含哨兵头结点。哨兵节点可以极大简化插入删除的逻辑但反转时要注意别把哨兵装进去。第二原链表是否可能被多个地方引用。如果原链表反转了而其他模块还持有原头指针这些指针会指向反转后的“尾节点”或某个中间节点造成逻辑混乱。必要时可以在反转前记录原头节点并通知持有引用的模块更新。第三内存管理。C中要记得释放不再使用的节点内存Python中则要关注是否还有任何变量引用原链表头避免垃圾回收滞后。这些已经超出了“写对一段反转代码”的范畴但它是“真正理解并熟练使用链表”的必经之路。很多人刷题能写得飞快一上工程就栽在内存、哨兵、引用更新这些问题上归根到底是只背了模板没有理解指针的本质。反向链表的每一步操作都是在和指针的“指向关系”较劲。把这种较劲的底子打好以后处理任何链表问题都会从容得多。根据我个人经验学习单链表反转最有效的方式不是一次次看题解而是自己从头推一遍先画一个三节点的链表用纸笔模拟迭代法每循环一步三个指针的走向再模拟递归法的“归”阶段如何把节点逐一接到后面。只要在纸上推过一遍再写代码的时候手和思路就都顺了。等到你的肌肉记忆能轻松写出无bug的迭代反转再去挑战K个一组、区间反转这些变形题你会发现自己已经完全不是原来的那个“背代码选手”了。