链表反转算法详解：掌握LeetCode 206的头插法迭代实现

反转单链表是算法与数据结构面试中的经典问题。本文将深入解析一种时空效率最优的迭代解法——头插法，其时间复杂度为O(n)，空间复杂度为O(1)。我们将从核心思路出发，逐步拆解代码，并通过表格演示整个过程。

一、理解基础概念与核心思路

在深入代码之前，我们先明确两个关键点。

1. 单链表的结构

链表中的每个节点（ListNode）包含两部分：

• val：存储节点的值。
• next：一个指针（或引用），指向下一个节点。链表的最后一个节点的 next 指向 null。

以链表 1 → 2 → 3 → 4 → null 为例，我们的目标是将它反转为 4 → 3 → 2 → 1 → null。

2. 头插法迭代思路

算法的核心在于使用三个指针，以迭代方式将原链表的节点逐个“移动”到新链表的头部：

• pre：始终指向新链表的当前头节点（初始为 null）。
• cur：指向原链表中当前待处理的节点（初始为原链表头 head）。
• nxt：一个临时指针，用于保存 cur 的下一个节点，防止链表断开。

循环过程可概括为：保存后路 → 反转指针 → 更新头节点 → 移动当前指针。

二、代码实现与逐行解析

以下是LeetCode 206的官方题解代码，我们为其添加详细注释。

class Solution {
    public ListNode reverseList(ListNode head) {
        // pre: 新链表的头节点，初始为空
        ListNode pre = null;
        // cur: 当前待处理的原链表节点，从头开始
        ListNode cur = head;

        // 当原链表还有节点未处理时，继续循环
        while (cur != null) {
            // 1. 保存后路：记录原链表的下一个节点，防止丢失
            ListNode nxt = cur.next;
            // 2. 反转指针：将当前节点指向前一个节点（即新链表的头部）
            cur.next = pre;
            // 3. 更新头节点：将新链表的头节点更新为当前节点
            pre = cur;
            // 4. 移动指针：处理原链表的下一个节点
            cur = nxt;
        }
        // 循环结束，pre指向反转后新链表的头节点
        return pre;
    }
}

三、分步演示：以 1→2→3→4→null 为例

通过下表，我们可以直观地跟踪每一步中指针和链表状态的变化。

初始状态（循环开始前）

指针	指向节点	原链表结构	新链表结构
pre	null	1 → 2 → 3 → 4 → null	null
cur	1
nxt	未定义

第一次循环（处理节点 1）

1. ListNode nxt = cur.next; → nxt 指向节点 2。
2. cur.next = pre; → 节点 1 的 next 指向 pre (null)，形成 1 → null。
3. pre = cur; → pre 更新为节点 1，新链表变为 1 → null。
4. cur = nxt; → cur 移动到节点 2。

指针	指向节点	原链表剩余部分	新链表结构
pre	1	2 → 3 → 4 → null	1 → null
cur	2
nxt	2

第二次循环（处理节点 2）

1. nxt = cur.next; → nxt 指向节点 3。
2. cur.next = pre; → 节点 2 的 next 指向节点 1，形成 2 → 1。
3. pre = cur; → pre 更新为节点 2，新链表变为 2 → 1 → null。
4. cur = nxt; → cur 移动到节点 3。

指针	指向节点	原链表剩余部分	新链表结构
pre	2	3 → 4 → null	2 → 1 → null
cur	3
nxt	3

第三次循环（处理节点 3）

1. nxt = cur.next; → nxt 指向节点 4。
2. cur.next = pre; → 节点 3 的 next 指向节点 2，形成 3 → 2。
3. pre = cur; → pre 更新为节点 3，新链表变为 3 → 2 → 1 → null。
4. cur = nxt; → cur 移动到节点 4。

指针	指向节点	原链表剩余部分	新链表结构
pre	3	4 → null	3 → 2 → 1 → null
cur	4
nxt	4

第四次循环（处理节点 4）

1. nxt = cur.next; → nxt 指向 null（原链表末尾）。
2. cur.next = pre; → 节点 4 的 next 指向节点 3，形成 4 → 3。
3. pre = cur; → pre 更新为节点 4，新链表变为 4 → 3 → 2 → 1 → null。
4. cur = nxt; → cur 移动到 null，循环条件 cur != null 不满足，循环结束。

指针	指向节点	原链表剩余部分	新链表结构
pre	4	null	4 → 3 → 2 → 1 → null
cur	null
nxt	null

循环结束后，pre 指向新链表的头节点 4，这正是反转后的链表头，最终返回 pre。

四、关键细节与常见疑问

1. 为什么必须使用 nxt 临时变量？

如果不先保存 cur.next，当执行 cur.next = pre 反转当前节点的指针后，我们就失去了通往原链表下一个节点的“路”。nxt 的作用就是提前保存这条路径，确保迭代可以继续。

2. 循环终止条件为什么是 cur != null？

cur 代表原链表中尚未处理的节点。只要 cur 不为空，就意味着还有节点需要反转；当 cur 变为 null 时，说明原链表已全部处理完毕。

3. 为什么返回 pre 而不是 cur？

循环结束时，cur 必定为 null（原链表遍历完的标志），而 pre 则指向最后一个被处理的节点，即反转后新链表的头节点。

4. 边界情况处理

• 空链表：head 为 null，cur 初始即为 null，循环不执行，直接返回 pre（初始值 null），正确。
• 单节点链表：只有一个节点 1→null，循环执行一次后，pre 指向节点 1，返回结果正确。

五、总结

头插法迭代反转链表的核心在于三个指针的精妙配合：

1. pre 管新家：始终维护反转后链表的头部。
2. cur 管拆迁：指向原链表中正在被“搬移”的节点。
3. nxt 管后路：确保原链表不会丢失。

整个过程遵循“保存下一个，反转当前，移动指针”的固定步骤，逻辑清晰且高效。理解此解法后，无论是应对面试还是提升算法思维，都大有裨益。若想加深理解，动手在纸上画出每一步的指针变化是最有效的方法。