反转链表算法详解：双指针与递归两种核心解法

1. 反转链表：从题目本质到两种核心解法

1.1 这道题到底在考什么

反转链表（LeetCode 206）大概是所有学算法的人绕不开的一道入门题。我当年跟着代码随想录刷题的时候，第一次看到这个题名觉得挺简单，结果上手一写就懵——链表反转不是把值倒过来，而是要把每一个节点的指针方向全部掉头。这个区别很关键。

题目给的是单链表的头节点 head，要求返回反转后的新头节点。比如 1 -> 2 -> 3 -> 4 -> 5，反转后变成 5 -> 4 -> 3 -> 2 -> 1。表面上看只是顺序颠倒，实际上涉及的是对所有 next 指针的重定向。链表节点在内存里并不是连续存放的，它靠指针串联，所以反转本质上就是“重新穿针引线”。

这道题适合谁来刷？我觉得只要你正在准备面试、刚开始学数据结构、或者想把递归和迭代的思想彻底搞清楚，都应该拿它开刀。它的代码量很少，但信息密度极大。你写完这道题，基本就理解了指针操作、循环不变量、递归的递推关系这三个核心概念。代码随想录里把这道题归为链表章节的经典题目，确实名副其实——它是后面很多复杂链表题（比如反转区间、K个一组反转）的基石。

1.2 双指针法的核心逻辑

双指针法的思路非常朴素：用两个指针 prev 和 cur 分别指向前一个节点和当前节点，每一步把 cur->next 指向 prev，然后两个指针同时前进。整个过程就像把一串项链的每个环扣重新扣到前一个环上。

具体来说：

• 初始时 prev = nullptr，cur = head。为什么 prev 是空？因为反转后原来的头节点会变成尾节点，它的 next 必须是空。
• 每一轮迭代要先把 cur->next 保存下来，否则一旦修改 cur->next，后面的节点就丢了。这个临时变量通常叫 next 或者 tmp。
• 然后令 cur->next = prev，完成当前节点的反转。
• 接着 prev = cur，cur = tmp，继续处理下一个节点。

这个思路里最容易被忽略的是那个 tmp。很多人第一次写，直接 cur->next = prev; prev = cur; cur = cur->next;，结果 cur 变成了自己，死循环出不来。原因就是 cur->next 已经被改了，原来的后继丢了。代码随想录里反复强调“先保后改”，这四个字就是双指针法的命门。

双指针法的时间复杂度是 O(n)，空间复杂度是 O(1)，因为只用了几个指针变量。这也是面试里最推荐的写法，干净利落，不容易出问题。

1.3 递归法的思路与等价性

递归法看起来更“聪明”，但理解起来也更绕。它的核心想法是：反转整个链表，可以拆成“反转头节点之后的部分，再把头节点接到尾部”。换句话说，如果我已经得到了 head->next 之后那段链表反转后的新头节点，我只需要让 head->next->next = head，再让 head->next = nullptr，就完成了整体反转。

举个例子，链表 1 -> 2 -> 3：

• 递归调用 reverse(2 -> 3)，返回反转后的头节点 3，此时链表变成 1 -> 3 -> 2（注意后半段已经被反转）。
• 回到节点 1，执行 2->next = 1，即 1->next->next = 1，链表变成 3 -> 2 -> 1。
• 再把 1->next = nullptr，结束。

这个过程中，递归函数返回的始终是“反转后的头节点”，也就是原来链表的尾节点。递归的终止条件是 head == nullptr 或者 head->next == nullptr，此时不需要反转，直接返回 head。

递归法的时间复杂度也是 O(n)，但空间复杂度是 O(n)，因为递归调用栈会占额外空间。不过它用代码表达了“分而治之”的思想，对理解递归很有帮助。代码随想录里把递归法和双指针法放在一起讲，就是想让你看到两种思维：一个是从前往后迭代调整，一个是从后往前递归返回。

2. 双指针法实操详解：从画图到代码

2.1 画图理解五步过程

我刷这道题最受益的习惯就是画图。不要嫌麻烦，拿纸笔把每一步指针变化画出来，比看十遍讲解都管用。以链表 1 -> 2 -> 3 -> 4 -> nullptr 为例，初始状态：

code复制prev = null
cur = node(1)
tmp = node(2) // 先保存

第一轮：

1. 把 cur->next 指向 prev，即 1->next = null，此时链表从 1 这里断开，2 -> 3 -> 4 还是完整的。
2. prev 前进到 cur，也就是 prev = node(1)。
3. cur 前进到 tmp，也就是 cur = node(2)。

注意，此时内存中 1 的 next 已经是 null 了，但 2 的 next 仍然指向 3。所以接下来的第二轮要先把 3 保存为 tmp，然后让 2->next = 1。依次类推。

到最后一步，cur 变为 nullptr，prev 指向原来的尾节点 4，此时 prev 就是反转后的新头节点。返回 prev 即可。

整个过程中，链表状态是这样变化的：

• 初始：prev = null, cur = 1
• 第一步后：1 -> null, 剩余 2 -> 3 -> 4
• 第二步后：2 -> 1 -> null, 剩余 3 -> 4
• 第三步后：3 -> 2 -> 1 -> null, 剩余 4
• 第四步后：4 -> 3 -> 2 -> 1 -> null

你会发现，我们其实是从链表的头部开始，一点点“拆”下来，再“反接”到前面。这跟数组反转完全不同——数组可以直接交换首尾元素，链表必须逐个改指针。

2.2 C++、Python、Java 三种代码实现

我用三种语言各写了一遍，方便你对照。先看 C++：

cpp复制class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* cur = head;
        while (cur != nullptr) {
            ListNode* tmp = cur->next;
            cur->next = prev;
            prev = cur;
            cur = tmp;
        }
        return prev;
    }
};

这段代码几乎就是双指针法的标准答案。注意 while 的循环条件是 cur != nullptr，当 cur 为空时说明所有节点都已反转完毕，此时 prev 正好指向新头节点。

再看 Python：

python复制class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        cur = head
        while cur:
            tmp = cur.next
            cur.next = prev
            prev = cur
            cur = tmp
        return prev

Python 里要注意，ListNode 类的属性是 next，不是 next 的指针概念，但逻辑完全一样。另外 Python 的变量赋值是引用，所以 tmp = cur.next 保存的是引用，修改 cur.next 不影响 tmp。

然后是 Java：

java复制class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode tmp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = tmp;
        }
        return prev;
    }
}

三者逻辑一模一样。我的经验是，你只要把 C++ 的版本吃透，其他语言就是换皮。面试时可以先用自己熟悉的语言写，再主动跟面试官说“我用另一种语言也可以实现”，还能加分。

2.3 边界条件与循环不变量

写这道题最容易挂的边界条件是“空链表”和“只有一个节点”。空链表时 head == nullptr，while 循环根本不会进入，直接返回 prev 也就是 nullptr，结果正确。只有一个节点时，cur->next 是空，tmp 保存空，然后 cur->next = prev（也就是空），prev = cur，cur = tmp（空），循环结束返回 prev，也就是原来的节点，结果也正确。

但很多人在边界条件上翻车是因为没有想清楚“循环不变量”。循环不变量是指每次循环开始时，prev 已经指向当前已经反转好的部分链表的头节点，cur 指向尚未反转部分链表的头节点，tmp 用于暂存 cur->next。在循环体内，这个不变量始终保持。代码随想录里把这些细节讲得很透彻，这也是我推荐照着它练的原因——很多人刷题只背代码，不思考不变量，换个变体题就废了。

还有一个隐藏细节：如果链表有环，这个算法会死循环。不过 LeetCode 206 的题面默认无环，面试时可以主动问一下“是否需要考虑环”，显得你考虑周全。如果需要处理环，可以用快慢指针判断环，或者记录访问过的节点。

3. 递归法：从底层思考到代码落地

3.1 终止条件与递推关系

递归法写起来特别短，但理解起来比迭代难。核心是搞清楚“递推关系”和“终止条件”。终止条件就是链表为空或只有一个节点：

cpp复制if (head == nullptr || head->next == nullptr) return head;

为什么这样写？因为空链表不需要反转，只有一个节点的链表反转后还是它自己。返回 head 即可。

递推关系是：newHead = reverseList(head->next)，也就是说先把后面那一段反转，拿到新的头节点。然后执行：

cpp复制head->next->next = head;
head->next = nullptr;

这两行是什么意思？head->next 在递归返回后，指向的是原链表中 head 的后继节点，假设叫 node2。此时 node2 已经是反转后那段链表的尾节点（因为递归处理的是 2 -> 3 -> 4，反转后 4 -> 3 -> 2，尾节点是 2，而 head->next 正指向这个 2）。所以我们让 node2->next = head，就把 head 接到了尾部。然后把 head->next 置空，因为 head 现在是新的尾节点。

这个操作非常精妙，但也很容易混淆。我一直用一句话记忆：“让下一个节点的 next 指向我，我再指向空。”几乎所有递归反转链表题都是这句话的变形。

3.2 递归代码实现与调试技巧

C++ 递归版本：

cpp复制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;
    }
};

Python 版本：

python复制class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        new_head = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return new_head

Java 版本：

java复制class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

调试递归代码有个好办法：在纸上展开调用过程。比如链表 1 -> 2 -> 3，逐步写出：

• reverseList(1) 调用 reverseList(2)
• reverseList(2) 调用 reverseList(3)
• reverseList(3) 返回 3（因为 3->next == null）
• 回到 reverseList(2)：head = 2，head->next 是 3，执行 3->next = 2，2->next = null，返回 3
• 回到 reverseList(1)：head = 1，head->next 是 2（此时 2->next 已经是 null），执行 2->next = 1，1->next = null，返回 3

这样一步步推，你就能看到递归的“归”过程是在回溯时完成指针反转的。

3.3 双指针与递归的对比选型

面试时到底用哪种？我建议优先双指针。原因有三：

• 双指针空间复杂度 O(1)，递归 O(n)，链表很长时递归可能栈溢出。
• 双指针的思路直观，不容易把自己绕晕，面试时不容易卡壳。
• 递归代码虽然短，但解释“为什么这么写”需要花更多口舌，万一你紧张讲不明白，反而减分。

但递归也有它的价值。很多链表题天然适合递归，比如“两两交换链表中的节点”“反转链表的前 N 个节点”，用递归思路写起来很简洁。所以我建议你两种都要会，但面试时先出手写双指针，如果面试官追问“还有别的方法吗”，再展示递归。

代码随想录里有一句话我特别认同：“递归是树的遍历的基础，链表递归是递推思想的练兵场。”把这道题练透，后面学二叉树的前中后序遍历，你会觉得顺很多。

4. 常见问题与避坑指南

4.1 我踩过的常见错误

先说我自己第一次写这道题时的错误：循环里忘了保存 cur->next，导致指针丢失。这个错误在 LeetCode 上报的是“Time Limit Exceeded”或者“Runtime Error”，其实就是链表变成了环。我调试了好久才发现，自己一直用 cur = cur->next，但 cur->next 早就被改成 prev 了。

另一个常见错误是把 return prev 写成了 return cur。循环结束后 cur 是 nullptr，返回空链表，直接错得离谱。所以记住：循环结束返回的一定是 prev。

还有一个边界问题是“节点数量为 0 或 1”时，prev 的初始化对不对。prev = nullptr 这个初值不能省，否则第一次反转 cur->next = prev 时会指向一个野指针（C/C++ 里尤其严重）。Java 和 Python 里不初始化为 null 会报编译错误，反而安全。

我整理了一个速查表：

4.2 面试中的延伸考点

反转链表这道题在面试里很少直接考，通常会被包装成更复杂的题。比如反转链表的第 m 到 n 个节点，或者 K 个一组反转链表。你只要把这道题的指针操作练熟，那些变体题其实就是在原来的基础上加几个条件。

还有一个高频变形题是“判断链表是否回文”。常见解法是找到中点、反转后半段、再逐节点比较。这个过程中反转链表就是核心步骤。所以刷完 206，你相当于解决了回文链表的半道题。

另外，“反转双向链表”也是常见的追问。双向链表每个节点有 prev 和 next 两个指针，反转时只需要交换这两个指针即可，但要注意遍历方向。比如：

cpp复制while (cur != nullptr) {
    swap(cur->prev, cur->next);
    cur = cur->prev;  // 注意，交换后 prev 指向原 next
}

这个变形能看出来你是不是真的理解了指针操作，还是只背了代码。

4.3 时间复杂度和空间复杂度分析

双指针法的时间复杂度是 O(n)，因为每个节点恰好被访问一次；空间复杂度是 O(1)，只用了 prev、cur、tmp 三个指针。递归法的时间复杂度也是 O(n)，但空间复杂度是 O(n)，因为递归调用栈的深度就是链表长度。

很多面试官会追问“为什么递归空间复杂度是 O(n)”。你要能解释：递归函数每调用一次，都会在调用栈上压入一层现场信息，直到递归到底才开始返回。所以对于长度为 10000 的链表，递归深度也是 10000，有可能导致栈溢出。这也是工程上更推荐迭代法的原因。

如果你用 Python 写递归，还要注意 Python 默认递归深度限制是 1000 左右，链表一长就报 RecursionError。所以除非题目明示链表很短，否则尽量不要在 Python 里用递归。

我的个人体会

刷完这道题最大的收获不是背会了代码，而是养成了“画图 + 写不变量”的习惯。后来刷二叉树、回溯、动态规划，我都坚持先画状态图，再写代码。反转链表的双指针法和递归法看似简单，却把“指针操作”和“递推思想”这两个基本功练得很扎实。

最后再分享一个小技巧：如果你在面试中写这道题，可以在代码里加一行注释，写上“tmp 用于暂存 cur->next，避免指针丢失”。面试官看到这行注释，会觉得你真的懂边界，而不是背题。

这道题值得反复刷三遍。第一遍照着思路写，第二遍凭记忆写，第三遍尝试不看代码自己推导，然后试一试用递归写。等你做到这一步，你再看反转链表相关的进阶题，会发现不过如此。