企业官网建设流程全解析

1. 反转链表到底在考什么

反转链表这道题，几乎成了所有刷题路线图里的第一道分水岭。很多人第一次看到它，觉得逻辑简单得不行——把箭头掉个头不就完了？结果真上手写代码，指针指来指去，跑出来要么死循环，要么断链，要么只反转了前两个节点。我见过不少同学在这道题上卡了一整个下午，最后对着答案抄了一遍，过两天再写还是写不出来。

问题的根子不在“思路”，而在指针操作的顺序感。反转链表的本质，是让你在一条单向通道上，把每个节点原本指向后方的指针，改成指向前方。听起来一句话，但真正动手时，你手里同时要抓住三个东西：当前节点、它的前一个节点、它的后一个节点。少抓一个，链就断了；抓的顺序不对，节点就丢了。

这篇文章我会把反转链表从“能写出来”到“写得稳、写得对、能举一反三”的完整路径拆开讲。适合两类人：一类是刚学完C语言指针、准备开始刷题的新手；另一类是写过几遍但每次都要重新推一遍、想彻底吃透的人。核心关键词就是链表、反转链表、C语言、指针操作，我会围绕这几个点，把迭代法、递归法、边界处理、调试技巧全部讲透。

先说一个我自己的判断：反转链表之所以经典，不是因为它难，而是因为它把“指针操作”这件事压缩到了一个极小的场景里。你在这个场景里犯的每一个错，在更复杂的链表题里都会被放大十倍。所以这道题值得反复写，写到闭着眼睛都能把三指针的移动顺序默出来为止。

2. 三指针迭代法：顺序就是一切

2.1 为什么必须是三个指针

先想一个最朴素的问题：如果只有一个指针指向当前节点，你能完成反转吗？

假设链表是 1 -> 2 -> 3 -> NULL，当前指针 cur 指向 1。你想让 1 指向 NULL，这没问题，把 cur->next 改成 NULL 就行。但改完之后，你怎么找到 2？原来的 1->next 已经被你覆盖掉了，2 的地址丢了。这就是单指针的死穴：修改指针之前，必须先保存它原来指向的东西。

那用两个指针够不够？一个 cur，一个 prev。cur 指向当前节点，prev 指向它前面那个。你执行 cur->next = prev，然后想把 cur 和 prev 都往后挪一位。prev 挪到 cur 没问题，但 cur 要挪到哪？cur 原来的 next 已经被你改成 prev 了，你找不到后面的节点了。

所以必须要有第三个指针，专门负责在改指针之前，把“下一个节点”先存下来。这就是三指针法的由来。三个指针各司其职：

注意：next 不需要在循环外初始化，它只在循环体内部有意义。这一点很多人会纠结，其实没必要。

2.2 循环体内四步走的固定节奏

三指针法的循环体，我习惯把它记成“存、改、移、移”四步。顺序绝对不能乱：

1. 存：next = cur->next，先把后面的路保住
2. 改：cur->next = prev，把当前节点的箭头掉头
3. 移：prev = cur，前指针推进到当前位置
4. 移：cur = next，当前指针推进到下一个待处理节点

这四步里，第一步和第二步的顺序是死规定。如果你先改 cur->next，再想存 next，存到的就是 prev 了，整条链从第二个节点开始全丢。第三步和第四步的顺序也不能反，如果先 cur = next 再 prev = cur，那 prev 就跑到 next 的位置去了，反转出来的链会错位。

用 C 语言写出来是这样：

struct ListNode* reverseList(struct ListNode* head) { struct ListNode *prev = NULL; struct ListNode *cur = head; struct ListNode *next = NULL; while (cur != NULL) { next = cur->next; // 存 cur->next = prev; // 改 prev = cur; // 移 cur = next; // 移 } return prev; }

循环结束时，cur 一定是 NULL，而 prev 指向原链表的最后一个节点，也就是反转后的头节点。所以返回 prev，不是返回 head。这一点新手特别容易搞错，因为直觉上会觉得应该返回 head。

2.3 手动跑一遍 1->2->3->NULL

光看代码不够，我建议每个初学的人都在纸上画一遍。我带你走一次：

初始状态：prev=NULL，cur=1，next=NULL。

第一轮：next 存到 2；1->next 改成 NULL；prev 移到 1；cur 移到 2。此时链表变成 1->NULL，2->3->NULL，prev 指向 1。

第二轮：next 存到 3；2->next 改成 1；prev 移到 2；cur 移到 3。此时 2->1->NULL，3->NULL，prev 指向 2。

第三轮：next 存到 NULL；3->next 改成 2；prev 移到 3；cur 移到 NULL。此时 3->2->1->NULL，prev 指向 3。

循环条件 cur != NULL 不成立，退出，返回 prev，也就是 3。整条链变成 3->2->1->NULL，完成。

这个过程我强烈建议手写三遍以上。不是抄代码，是画图加标注指针。画到你能预判每一步三个指针分别在哪，这道题才算真正过了。

2.4 边界情况：空链表和单节点

很多人写代码只测 1->2->3，不测空链表和单节点，结果一提交就挂。

空链表：head = NULL。进循环前 cur = NULL，while 条件直接不成立，循环体一次都不执行，返回 prev = NULL。正确。

单节点：head 指向唯一节点，它的 next 是 NULL。第一轮：next = NULL；cur->next = prev = NULL（本来就是 NULL，没变化）；prev = cur；cur = NULL。退出，返回 prev，也就是那个唯一节点。正确。

所以三指针法天然处理了这两个边界，不需要额外加 if 判断。这是它比某些递归写法更省心的地方。

3. 递归法：从后往前想的思维切换

3.1 递归的核心假设

迭代法是从前往后处理，递归法反过来，从后往前。递归写链表题的通用心法是：假设后面的部分已经处理好了，我只负责把当前这一层接上。

具体到反转链表，递归函数的定义是：给我一个头节点，我把这条链表反转，并返回反转后的新头节点。那么对于 head 来说，我递归调用自己处理 head->next，拿回来的就是后半段反转后的新头。此时 head->next 这个节点，已经变成了后半段的尾节点。我要做的，就是让这个尾节点指向 head，再让 head 指向 NULL。

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; }

这两行是递归法的灵魂：

• head->next->next = head;让后面那个节点反过来指向我
• head->next = NULL;把我自己的 next 断掉，避免成环

3.2 为什么递归终止条件是两个

if (head == NULL || head->next == NULL)这个条件，两个判断缺一不可。

head == NULL 处理的是空链表，直接返回 NULL。head->next == NULL 处理的是单节点，或者递归到了原链表的最后一个节点。到了最后一个节点，它没有后面的部分可以反转，它自己就是反转后的头，直接返回自己。

如果只写 head->next == NULL，空链表进来会直接对 NULL 取 next，程序崩溃。如果只写 head == NULL，单节点进来会继续递归，然后对 NULL 操作，同样崩溃。

3.3 递归的调用栈长什么样

以 1->2->3->NULL 为例，递归的展开过程是这样的：

reverseList(1) 调用 reverseList(2)，reverseList(2) 调用 reverseList(3)，reverseList(3) 发现 3->next == NULL，返回 3。

回到 reverseList(2) 这一层：newHead = 3。执行 2->next->next = 2，也就是 3->next = 2；然后 2->next = NULL。此时 3->2->NULL，返回 newHead = 3。

回到 reverseList(1) 这一层：newHead = 3。执行 1->next->next = 1，也就是 2->next = 1；然后 1->next = NULL。此时 3->2->1->NULL，返回 3。

每一层只做两件事：让后面的节点指向自己，然后断开自己的 next。层层返回，最后 newHead 一路传回最外层。

3.4 递归法的空间代价

递归法代码短，但有一个必须知道的代价：空间复杂度是 O(n)，因为调用栈的深度等于链表长度。链表有一万个节点，递归就压一万层栈。在 C 语言里，默认栈空间有限，链表特别长的时候递归会栈溢出。

迭代法空间复杂度是 O(1)，只用了三个指针。所以工程实践中，如果链表长度不可控，优先用迭代法。递归法更适合用来理解“从后往前”的思维，面试时如果面试官不限制，写递归也能过，但你要能说清楚它的空间开销。

4. 那些让我卡住的坑和排查方法

4.1 返回 head 而不是 prev

这是最高频的错误。代码逻辑全对，最后 return head，结果只输出了原链表的第一个节点。原因很简单：反转之后，原来的 head 已经变成了尾节点，它的 next 是 NULL。你返回它，等于只返回了一个节点。

排查方法：在 return 之前打印 prev 和 head 的值，看看它们分别指向哪。如果 prev 指向原链表最后一个节点，head 指向第一个节点，那就说明你该返回 prev。

4.2 循环里先改后存导致断链

把next = cur->next和cur->next = prev写反，是第二高频错误。写反之后，cur->next 已经被改成 prev，你再存 next，存到的就是 prev。下一轮 cur 移到 prev 的位置，整条链开始往回绕，要么死循环，要么只反转了第一个节点。

排查方法：在循环体里加一行打印，输出 cur 的值和 next 的值。如果发现 next 的值等于 prev 的值，那就是顺序反了。

4.3 递归忘记断开 head->next

递归法里只写了head->next->next = head，忘了head->next = NULL。结果是原链表的第一个节点和第二个节点互相指向，形成环。输出的时候会无限循环。

排查方法：反转完成后，遍历链表并计数，如果发现节点数超过原长度，或者遍历不终止，就是成环了。也可以用一个集合记录访问过的节点地址，重复出现就是有环。

4.4 用纸笔调试比用 IDE 更快

我自己的经验是，链表题在脑子里推容易乱，在 IDE 里打断点又太重。最快的办法是拿一张纸，画三个方框代表三个指针，每执行一步就移动方框的位置。画三遍之后，你对指针移动的节奏会有肌肉记忆。

提示：如果你在面试现场，没有纸笔，可以用手指在桌面上比划。三个手指分别代表 prev、cur、next，边比划边说出每一步在干什么。面试官通常很吃这一套，因为这说明你真的理解指针，而不是背代码。

5. 从反转链表延伸出去的三类变体

5.1 反转前 N 个节点

有时候题目不是反转整条链，而是反转前 N 个。这时候迭代法的循环条件从cur != NULL改成计数到 N 就停。递归法的终止条件也要相应调整，从“到最后一个节点”改成“到第 N 个节点”。

核心变化在于：你需要一个计数器，或者一个递减的 N。每处理一个节点，N 减一，减到 0 就停。返回的头节点是第 N 个节点，而不是原链表的最后一个节点。

5.2 反转指定区间 [m, n]

这是反转链表的进阶版，也是面试高频题。思路是先用一个指针走到 m-1 的位置，把区间的前一个节点记下来，然后对区间内的节点做反转，最后把前一个节点接到反转后的头上，把反转后的尾接到 n+1 的位置。

这道题的坑在于边界：m 等于 1 的时候，没有前一个节点，需要引入一个虚拟头节点（dummy node）。虚拟头节点的 next 指向 head，这样无论 m 是多少，m-1 位置永远存在。

5.3 K 个一组反转链表

这道题是反转链表的终极形态。每 K 个节点为一组，组内反转，组间保持原顺序。如果最后不足 K 个，保持原样。

解法是：先数出链表总长度，然后每 K 个一组调用反转函数。反转函数需要返回新的头和新的尾，方便和前后组拼接。这道题写下来大概四五十行，是检验你是否真正掌握反转链表的试金石。

6. 我刷这道题的真实节奏

最后说点实在的。反转链表这道题，我前前后后写了不下二十遍。第一遍看答案，第二遍照着答案默，第三遍合上答案自己推，第四遍开始尝试递归，第五遍开始做变体。真正让我觉得“通了”的瞬间，不是我能默写出代码，而是我能对着一个空链表，在脑子里把三个指针的移动过程完整演一遍，不出错。

如果你现在还在卡这道题，我的建议是：不要急着看下一道。把迭代法写五遍，每一遍都在纸上画指针。然后隔一天再写一遍，隔三天再写一遍。如果三次都能一次写对，这道题才算真正过了。

C 语言写链表还有一个隐藏的好处：它逼着你直面内存和指针。很多用高级语言刷题的人，对指针的理解是模糊的，因为语言帮你屏蔽了细节。但链表题的核心恰恰就是指针操作，你用 C 写一遍，再用其他语言写，会发现理解深度完全不一样。

提示：写链表题的时候，养成一个习惯——每分配一个节点，就想一下它什么时候被释放。虽然刷题时内存泄漏不影响判题，但这个习惯在真实项目里能救命。

反转链表之后，我建议紧接着刷“合并两个有序链表”和“删除链表的倒数第 N 个节点”。这三道题合在一起，基本覆盖了链表操作的所有基本模式：指针反转、双链合并、快慢指针。把这三道吃透，链表这一块就不会再有大的障碍了。