反转链表：迭代与递归双写法

反转链表（LeetCode 206）是链表的基本功，也是回文链表、K 个一组翻转等进阶题的子步骤。这一篇把迭代、递归两种写法都写透，再看两个以它为原型的变体题。

一、双指针迭代（LeetCode 206）

1.1 核心动作

反转的本质：遍历过程中，把每个节点的 next 从"指向后继"改成"指向前驱"。要完成这个动作需要三个信息：

cur：当前正在掉头的节点；
prev：cur 的前驱，反转后就是 cur 新的 next；
next：临时变量，先存下 cur 原来的后继，否则改完 cur.next 这条路就断了。

1.2 逐步图解

以 1 -> 2 -> 3 -> null 为例，初始 prev = null、cur = head：

初始:    null   1 -> 2 -> 3 -> null
         prev  cur
 
第1轮:  1.next 改指 prev（null），然后 prev=1, cur=2
        null <- 1    2 -> 3 -> null
               prev  cur
 
第2轮:  2.next 改指 1，然后 prev=2, cur=3
        null <- 1 <- 2    3 -> null
                    prev  cur
 
第3轮:  3.next 改指 2，然后 prev=3, cur=null
        null <- 1 <- 2 <- 3
                          prev  cur(null) 循环结束
 
返回 prev（= 3，新的头）

每一轮都是固定四步：存后继、掉头、双指针整体右移。

1.3 代码

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next; // 1. 先存后继，防止断链
            cur.next = prev;          // 2. 掉头：指向前驱
            prev = cur;               // 3. prev 前进一格
            cur = next;               // 4. cur 前进一格
        }
        return prev; // cur 为 null 时，prev 就是新头
    }
}

容易疑惑的点：为什么返回 prev 而不是别的？看图上最后一轮——cur 已经走到 null，prev 停在原来的尾节点上，它就是反转后的头。

二、递归写法

2.1 回溯视角

递归的思路换了个方向：先把后面的链表全部反好，再回来处理当前节点。

递归定义：reverse(head) 返回"以 head 开头的链表反转后的新头"。
递归到最深处（尾节点）时开始回溯；回溯过程中，对当前节点做一件事：让后继指回自己。

假设后面已经反好:
    1 -> 2 <- 3            （3 是反转后的头，1.next 仍是 2）
              ^ 回溯时补两刀：
    1.next.next = 1  即 2.next = 1
    1.next = null
结果: null <- 1 <- 2 <- 3，返回 3

head.next.next = head 这一行是精髓：head.next 是自己的后继，再往后指就是让后继的 next 指回自己，完成"接回去"。

2.2 代码

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;         // 新头一路透传回顶层
    }
}

2.3 两种写法对比

维度	迭代（双指针）	递归
时间复杂度	O(n)	O(n)
空间复杂度	O(1)	O(n)，递归调用栈
思维方式	正着走、边走边改	先走到尾、回溯时改
实战建议	默认写法	理解回溯思想的练习

时间都是 O(n)，差别在空间：递归每层调用要占栈帧，链表长时可能触发 StackOverflowError。面试中默认写迭代，被要求"再写个递归"时再切换。

三、变体一：两两交换（LeetCode 24）

题目：两两交换相邻节点，如 1 -> 2 -> 3 -> 4 变成 2 -> 1 -> 4 -> 3。

这道题"反转"的味道变淡了，dummy 的味道变浓了：交换第一对时，头结点会从 1 变成 2，而 dummy 恰好能抹平这个特例。

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(-1, head);
        ListNode prev = dummy; // 每一对的前驱
 
        while (prev.next != null && prev.next.next != null) {
            ListNode first = prev.next;
            ListNode second = first.next;
 
            // 三步交换：prev 接 second，first 接 second 的后继，second 接 first
            prev.next = second;
            first.next = second.next;
            second.next = first;
 
            prev = first; // first 已变成这一对的尾巴，是下一对的前驱
        }
        return dummy.next;
    }
}

交换过程的指针变化（建议对照图画一遍）：

交换前:  prev -> 1 -> 2 -> 3
交换中:  first=1, second=2
         prev -> 2 -> 1 -> 3
         (prev.next=second, first.next=second.next, second.next=first)
交换后:  prev 移到 1，处理下一对

这题的易错点是三步的顺序：一旦先把 first.next = second.next 写在最前面，second 的原入口就丢了。口诀是**"谁被摘下来，谁的后继先备份"**。

四、变体二：K 个一组反转（LeetCode 25）思路概览

题目：每 k 个节点一组进行反转，不足 k 个的尾部保持原样，如 1 -> 2 -> 3 -> 4 -> 5（k=3）变成 3 -> 2 -> 1 -> 4 -> 5。

完整实现偏长，这里只建立框架认知，它其实是两个已学模型的组合：

dummy 起手：第一组反转后头结点会变，dummy 统一处理（和 24 一样）。
每次循环做三件事：
- 从当前组起点出发，探出 k 个节点，凑不齐就收工；
- 记录组尾（即组起点），把这一段套用 206 的反转逻辑原地反转；
- 把反转后的子链重新接回前后：前驱接新头，旧头（现组尾）接下一组起点。

关键点只有一个：反转一段链表前后，组的头和尾互换角色，接回去时别接反。把 206 写熟之后，这题就是把它的代码挪进一个 while 循环，再包上"凑组、接线"的壳。

五、小结

206 迭代四步（存后继、掉头、双移）是肌肉记忆级的基本功；
递归写法理解 head.next.next = head 的回溯含义即可，工程上用迭代（O(1) 空间，无栈溢出风险）；
24 和 25 是"反转 + dummy"的组合拳：前者练成对操作，后者练分段反转后的重新接线。

下一篇文章进入双指针的另一个用法：快慢指针判环。

参考

代码随想录 · 链表专题