企业官网建设流程全解析

先说句实在话：我在刷LeetCode的第三年回头看，反转链表这道题大概是我见过“性价比”最高的一道基础题。它稳坐LeetCode热门100题榜单多年，几乎所有面试题库里都有它的身影，但真正能把它讲清楚、写利索的人，远比你想象中少。因为它名义上考的是指针操作，实际上考的是你对“链表遍历过程中如何保存后路”这个核心心法有没有直觉。

这篇我打算把206反转链表从题目理解、迭代法、递归法、复杂度，一直讲到反转区间和K个一组翻转这些变体题，把我踩过的坑和带新人时反复强调的细节全部写出来。你可以直接当一篇刷题笔记用，也可以作为面试前的查漏补缺清单。

1. 题目到底在考什么

1.1 先看懂输入输出

题目本身非常短：给定单链表头节点head，反转链表，返回反转后的链表头。

输入：1 -> 2 -> 3 -> 4 -> 5 -> NULL 输出：5 -> 4 -> 3 -> 2 -> 1 -> NULL

我第一次刷这道题时，脑子里的第一反应是“这不就是把链表倒序打印一遍嘛”。但你注意，题目说的是反转链表，不是倒序输出。这里面的差别就是这道题和“水题”之间的分界线：你必须真实地改动每个节点的next指针，让原来指向后继的指针反过来指向它的前驱，而不是简单地把节点里的val倒着打印一遍。

为什么不能靠交换val实现？因为链表节点在实际业务中往往不是只有一个int。真实场景里节点可能携带一个很大的对象、一条日志、一段配置数据，你要反的是一个“整体结构”，而不是几个值。面试官把这道题放进来，想看的正是你对“指针/引用”这种底层操作的控制力，而不是你有多会交换变量。

理解这一点之后，你才会明白一个关键结论：反转链表这件事，本质上不是“移动数据”，而是“重排指针方向”。从头节点开始，每个节点的next都要掉头，指向它的前驱，原链表头变成新链表尾，原链表尾变成新链表头。

1.2 链表操作的铁律：改指针前先留后路

链表和数组最大的区别，数组有随机访问能力，你随时可以回头去取任何下标的值；链表只有一条攀爬的藤蔓——next指针。你手里只握着当前节点，一旦把当前节点的next改了，原来的后继可能就找不到了。

所以链表操作有一条铁律：任何一步修改next之前，先确认你之后还需要不需要原来的next。需要，就先把它存下来。

反转链表正是这条铁律最典型的应用现场。很多人写这道题翻车，不是不懂逻辑，而是改了cur->next之后，原来的下一个节点不见了，循环没法继续。这一点可以用生活里的动作来类比：你在一条单行道上往前走，想掉头往回走，得先记住身后这条路通向哪里，不能一转身就把导航关掉。

有了这个心法打底，接下来看迭代法和递归法，都会顺很多。它们本质上是同一个心法的两种表达方式：一个用显式的临时指针保存后路，一个用递归栈的层间返回隐式地保存后路。

2. 迭代法：三指针逐步掉头

2.1 核心思路：每走一步，就把箭头掉过来

迭代法的思路一句话就能讲完：维护pre和cur两个指针，从头开始，每到一个节点就把cur->next从指向下一个节点，改成指向前一个节点pre，然后pre和cur同时前进一格。

初始状态是pre指向NULL，cur指向head。为什么要让pre一开始就指向NULL？因为反转完成之后，原链表的头节点会变成新链表的尾节点，而尾节点的next本来就该是NULL。这个NULL不是摆设，它是新链表最后一个节点的正确归宿。

每一轮循环做四件事：

1. 用next暂存cur->next。
2. 把cur->next反向指向pre。
3. pre前进，变成当前cur。
4. cur前进，变成刚才暂存的next。

循环结束的条件是cur走到NULL。此时pre正好停留在原链表最后一个节点上，也就是反转后新链表的头，直接返回pre就完成了。

我每次带新人学这道题，都建议先别打开编辑器，拿张纸画三个节点，手动把pre、cur、next三个指针标好，走三轮循环。这一步画通了，代码对你来说就是顺水推舟，而不是死记硬背。

2.2 代码实现与逐行拆解

C++版本：

class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* pre = nullptr; ListNode* cur = head; while (cur != nullptr) { ListNode* next = cur->next; // 第一步：保存后路 cur->next = pre; // 第二步：掉头 pre = cur; // 第三步：pre前进 cur = next; // 第四步：cur前进 } return pre; } };

Java版本几乎逐字相同：

class Solution { public ListNode reverseList(ListNode head) { ListNode pre = null; ListNode cur = head; while (cur != null) { ListNode next = cur.next; cur.next = pre; pre = cur; cur = next; } return pre; } }

Python版本：

class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: pre, cur = None, head while cur: nxt = cur.next cur.next = pre pre = cur cur = nxt return pre

我拿C++版本逐行拆一下。

ListNode* pre = nullptr;这行看似平凡，实际是整道题最容易埋雷的地方。如果你把pre初始化为head，反转完成后新链表的尾节点就会指向head自己，形成一个环。这个环在判题时不会直接报“错误答案”，而是表现为Time Limit Exceeded，因为遍历根本走不完。我之前见过一个同学，代码逻辑全对，就是这里多了一个看似无害的初始化，卡了一个下午。

ListNode* next = cur->next;这行就是前面说的“保存后路”。它必须出现在修改cur->next之前。一旦你把这两行的顺序调换，原链表的后继就彻底丢了，程序要么断裂、要么形成无法预料的指向。这个顺序问题，在面试写白板的时候特别容易手滑，我建议你默写代码的时候养成肌肉记忆：先存next，再改指向。

cur->next = pre;这行是真正执行反转的一步。它让当前节点的指针掉头，指向之前已经处理好的部分链表的头。注意，此时pre指向的是一段已经完全反转好的链表，cur->next指向它之后，当前节点就成功“接”到了反转链表的头部。

pre = cur; cur = next;这两行是同步前进。它们的顺序不能换：如果先执行cur = next，pre就会停在原地，后续所有节点的反转都会出问题。你可以把pre和cur想象成两节连接在一起的车厢，pre是前面的车厢，cur是后面的车厢，每次前进必须保持这个相对顺序。

2.3 迭代法最容易写错的三个位置

第一个陷阱，忘了用next暂存cur->next。这是最高频的错误，没有之一。因为链表没有“回头索引”能力，一旦next丢失，整个链表的后半截就悬空了。

第二个陷阱，返回值写错。循环结束之后，cur已经变成NULL，pre才是最后一个有效节点，也就是新链表的头。误返回cur的人不在少数，一提交就发现“我的输出怎么是null”。

第三个陷阱，pre的初始值写成head。这个错误前面说过了，它不产生编译错误，也不直接产生逻辑错误，但会让新链表变成带环结构，最终报超时。如果你遇到“反转链表提交超时”的情况，第一反应不应该是怀疑算法复杂度，而是检查链表里有没有环。

3. 递归法：让系统栈替你记录前驱

3.1 递归的终止条件怎么定

迭代法是用显式的pre指针记录前驱。递归法则换了一种思路：我不手动维护pre，而是让递归调用栈帮我一层一层记住“当前节点的前驱是谁”。

假设我调用reverseList(head->next)，它返回的是“以head->next为头节点的子链表反转后的新头”。在此基础上，我只需要做两件事：把head接到这个子链表的尾巴上，然后把head原来的next断掉。

递归的终止条件有两种常见写法，我推荐双条件：

if (head == nullptr || head->next == nullptr) { return head; }

如果只写head == nullptr，那么链表走到最后一个节点时，递归还需要再多调用一层，让最后一个节点再把null传回来，白白多了一次入栈出栈。而加上head->next == nullptr之后，最后一个节点会直接作为反转后的头部返回，递归立刻回弹。这个优化在链表长度为100时感觉不出来，但一旦链表长度上万，能明显减少函数调用次数。

3.2 递归代码逐行解读

class Solution { public: 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; } };

初学者最大的困惑集中在这三行：

ListNode* newHead = reverseList(head->next);这行调用之后，newHead指向的是原链表最后一个节点。整个子链表内部已经被完全反转了，你可以认为“从head->next开始的这一段”已经是正序排列好的新链表。

head->next->next = head;这行是真正的反转动作。此时head->next这个节点既是子链表反转前的头，也是子链表反转后的尾。既然它是尾，它的next就应该是nullptr（或者此时刚好可以被赋值为head）。这一行的意思就是：把子链表反转后的尾节点指向当前head，让当前head成为新链表的新尾巴。

head->next = nullptr;这行断开当前head原本指向下一个节点的连接。如果不断开，反转完成后链表会带着环，这在递归版本里尤其隐蔽。很多人在递归版忘记这一步，结果提交之后报超时，回头检查逻辑怎么都对，其实就是这里漏了。

我再用一个稍微展开的方式说明为什么这三行不会互相打架：当你在head这一层执行head->next->next = head时，head->next这个节点就是上一层递归已经处理完的“反转后子链表的尾节点”。这一步给这个尾节点补上了向下一个节点的连接。而sub链表内部的其他连接，在上一层递归里已经全部完成了，你不需要再操心。这正是递归的优雅之处：每一层只处理自己的局部连接。

3.3 递归过程模拟：用1->2->3走一遍

我仍然建议你用纸笔画，但文字模拟一遍也很有帮助。

对链表1->2->3->NULL调用reverseList(1)：

第一层，head=1，head->next=2，不满足终止条件，调用reverseList(2)。 第二层，head=2，head->next=3，继续调用reverseList(3)。 第三层，head=3，head->next=nullptr，触发终止条件，直接返回3。

回到第二层：newHead=3。执行2->next->next=2，也就是3->next=2。再执行2->next=nullptr。返回3。

回到第一层：newHead=3。执行1->next->next=1。注意此时1->next还是2，2->next已经被上一层改成了nullptr，所以这里实际上是设置2->next=1。再执行1->next=nullptr。返回3。

最终从3开始：3->2->1->NULL。

如果你第一次看这个过程觉得绕，很正常。递归的难点就在于“同时存在多层调用，且每层修改的是同一批节点”。但一旦你接受了这个设定，递归版反而比迭代版更好记：终止条件，递归调用，反向连接，断开旧连接，返回新头。五步背下来就能写。

4. 复杂度分析为什么面试官穷追不舍

4.1 时间与空间复杂度的计算方式

复杂度分析是面试必问。反转链表恰好是一个“时间相同、空间不同”的绝佳对比案例。

迭代法的时间复杂度是O(n)。循环从head走到NULL，每个节点在循环体内被处理一次，每次都只做常量次操作，所以总操作次数和节点数成线性关系。空间复杂度是O(1)，因为额外变量只有pre、cur、next三个指针，不随链表长度变化。

递归法的时间复杂度同样是O(n)，每个节点依然只被访问一次。但空间复杂度变成O(n)，原因是递归调用栈。每一次调用reverseList都会在系统栈上分配一层帧，保存参数head、返回地址、局部变量newHead等信息。链表有n个节点，递归深度就是n，同时存在的栈帧数量就是n，所以额外空间是O(n)。

面试官在听到这里之后，很喜欢追问一个“陷阱题”：有人会说“我的递归函数里没有创建数组，为什么空间复杂度不是O(1)”。答案是：函数调用本身会消耗栈空间，这个栈空间是运行时系统自动分配的，虽然不是你在代码里显式写的，但依然是算法的额外成本。这个例子能很好地区分“理解空间复杂度”和“背空间复杂度”的候选人。

4.2 递归栈深度和尾递归优化

如果链表长度是10万，递归法在默认栈大小下大概率会栈溢出。这也是为什么在生产代码里处理大规模链表时，我几乎不用递归版反转链表，而迭代版永远稳如泰山。

还有一个高频追问：递归法能不能通过“尾递归优化”把空间降到O(1)？

答案是不能，因为反转链表的递归调用后还有操作要做。尾递归的定义是递归调用作为函数的最后一个操作，调用结束后可以直接返回，不再有任何额外动作。但这里reverseList(head->next)返回之后，还要继续执行head->next->next = head和head->next = nullptr这两步，所以它根本不是尾递归，编译器自然无法优化。就算你把代码改成尾递归风格，解决这个问题也需要额外引入一个accumulator参数来保存前驱，那样写出来的代码，其实已经在模拟迭代法了。

4.3 面试回答模板

如果面试官让你比较两种写法，我建议按照这个逻辑回答：

“迭代法空间O(1)，时间O(n)，性能稳定，不依赖语言和编译器的优化行为，工程上我优先选它。递归法代码更简洁、可读性更好，但空间O(n)，而且这道题的递归不是尾递归，传不了优化这层保护伞。面试时如果时间充裕，我会先给迭代法，再补充递归法作为思路对比，同时主动说明两者的复杂度差异。”

这样回答展示的不只是“我会写”，而是“我知道自己在写什么”。

5. 从一道题到一串题：反转链表的所有变体

5.1 先反转前N个节点

206能玩出的第一个变体叫“反转前N个节点”。比如链表是1->2->3->4->5，N=3，目标是输出3->2->1->4->5。

这个题没有独立的剑指Offer编号，在LeetCode上是作为“反转区间”的中间步骤出现的，但它却是理解后面所有变体的关键。

实现思路是在206的基础上增加一个“第N个节点的下一个节点”的保存逻辑。因为只反转前N个节点时，反转后的尾节点需要接回原链表的后半段。这个后半段必须在递归基里先存下来：

ListNode* successor = nullptr; // 记录第N个节点的下一个节点 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; }

这里的successor是一个成员变量或全局变量，作用是在递归到第N个节点时，把它背后的链表尾巴保存下来。等递归逐层回弹时，每层都会把当前节点的next指向successor，但真正的生效点在最终层：原链表的第1个节点会变成反转后的尾节点，它的next会正确指向第N+1个节点。你可能会想：“那中间层为什么要设head->next = successor？”因为中间层确实也会执行这一步，但由于后续还有更上层的递归在改head->next->next，最终只有最上层的head->next会停留在successor上。这个“最终覆盖”效应，是递归版特有的行为。

5.2 区间反转：LeetCode 92

有了reverseN，LeetCode 92“反转链表II”就水到渠成了。题目要求反转从位置m到位置n的区间，m和n都是从1开始计数的。

解法非常巧妙：如果m等于1，那问题就退化成刚刚的reverseN。如果m大于1，我们就让head向后挪动，同时把m和n都减1，直到m变成1：

ListNode* reverseBetween(ListNode* head, int m, int n) { if (m == 1) { return reverseN(head, n); } head->next = reverseBetween(head->next, m - 1, n - 1); return head; }

这个写法中，为什么n也要跟着减1？因为n是“相对于当前head”的偏移量。你从头节点向后走一步之后，第n个节点离当前节点的距离就少了1。如果你只减m不减n，递归到下一层时reverseN收到的参数就会偏大，导致反转范围超出预期。

这个变体和206一起复习，效果特别好。它逼着你想清楚“区间起点”“区间长度”和“链表位置偏移”三者之间的关系，而想清楚这三者之后，你对递归的理解会上一个台阶。

5.3 两两交换与K个一组翻转：LeetCode 24和25

再往后延伸就是LeetCode 24“两两交换链表中的节点”和LeetCode 25“K个一组翻转链表”。这两道题的内部反转逻辑依然来自206，只是多了一个“分组”动作。

K个一组翻转的思路是：先把链表分成若干个长度为K的小组，每个小组内部用反转链表的逻辑处理，再把反转后的组与前后组连接起来。这个过程中最容易断链的位置，是组与组之间的连接。因为反转后，原组内的尾节点变成了新组头，原组头变成了新组尾，你必须记录好上一组的尾节点和下一组的头节点，才能把它们接上。

我给你的练习建议是：先把206写到烂熟，时刻可以不假思索地写出三指针迭代版，然后再碰24和25。否则你一边考虑分组边界，一边还要处理反转逻辑，很容易两头都乱。

这里额外说一句：我在整理笔记时发现，把206、92、24、25这四道题放在一起刷，是理解“递归+迭代混合用法”性价比最高的路线。它们共用一套核心逻辑，只是不断叠加条件，非常锻炼对链表结构的掌控力。

6. 实战经验：我从这道题里学到的三件事

6.1 从“看懂”到“默写”，中间隔着三遍手画

我见过很多人看题解时秒懂，合上书就空白。反转链表尤其如此。我的经验是：看懂不算会，能默写才算入门。

我自己用三轮来巩固：

第一轮，照抄一遍题解，抄完立即关掉代码，凭记忆默写。第一次默写大概率会在next取值的位置卡壳，这很正常，卡住的地方就是你真正薄弱的地方。

第二轮，拿一个长度为3的链表，在纸上手动模拟迭代版本的每一步。把pre、cur、next三个指针分别用不同颜色的笔标出来，每执行一次循环，就把指针的移动轨迹画一遍。这一步能帮助你建立对“后路”的直觉。

第三轮，尝试自己推导递归版本，并且用1->2->3为例子，手动展开递归树，标出每一层的head、head->next和新newHead。通过这个方式，你能真正理解递归版的“回弹”过程。

三轮下来，这道题才算长在你身上了。

6.2 常见错误速查表

我在带新人时，把反转链表最常见的错误整理成了一张表，遇到问题直接按表排查：

错误现象 | 可能原因 | 排查与解法 提交后返回null | 循环结束时return了cur | 循环结束后cur为NULL，应return pre 编译提示cur未定义 | 循环前漏了ListNode* cur | 在循环前定义并赋值为head 链表打印出现循环，提交超时 | pre初始化为head或递归版漏了head->next=nullptr | 检查是否在原链表头处形成环 反转后链表只剩第一个节点 | 修改cur->next之前没存next | 用next = cur->next后，再执行cur->next = pre 递归深链表时栈溢出 | 链表太长且用了递归版 | 改用迭代法；或检查终止条件是否包含head->next==nullptr

这张表是我反复吃亏后的总结，你刷题时可以直接把它贴在旁边。

6.3 刷题路线与题型交叉建议

206反转链表做完之后，我建议顺着下面这条线往下刷，递进关系非常清晰：

206反转链表 -> 92反转区间 -> 24两两交换 -> 25K个一组翻转 -> 234回文链表 -> 143重排链表

这六题共用一套链表指针操作功底。206是地基，92和24是延展，25是综合应用，234和143则是把链表反转当作一个工具去解决更复杂的问题。花一周时间吃透这条线，收益比零散刷五十道简单题大得多。

最后多说一句关于题型交叉的感受。我日常刷题会把链表题和二分查找类题交替安排，比如连着刷完206之后，第二天去碰一下LeetCode 073“爱吃香蕉的狒狒”那种二分答案题。原因很简单：这两种题型是完全相反的思维模式。链表题盯着指针指向，二分题盯着边界值。交叉刷能防止思维僵化，也更容易在面试里快速切换状态。

提示：如果你刷题时间有限，只想先啃一块硬骨头，链表专题是性价比最高的起点之一。它题目数量不多，但每种操作都足够经典，而且几乎不会出现“看完就忘”的问题——因为它的核心心法太明确了：改next前先留后路。

我个人这几年的体会是，反转链表这道题真正的门槛不在“反转”这两个字，而在“链表操作中，每个节点的next是唯一的通道”。一旦你形成了“动通道前先备份”的本能，这道题就变成了一套机械动作，闭着眼睛都能写对。递归版本虽然代码更短，但我还是建议你把它当作思维训练来理解，它不会比迭代版更好用，但它能帮你把递归的回弹逻辑练透，之后刷树、刷图都会顺很多。

这道题我每隔一段时间都会重新写一遍，每次写都能发现自己对指针或是递归的理解又深了一层。如果你今天只是看完了这篇，建议立刻打开编辑器，手画一遍指针图，再默写一遍三个版本。画通那一刻，你会明白它为什么能稳坐LeetCode热门100题的位置那么多年。