反转链表 图解题解

这道题真正在问什么

给单链表的头节点 head，把每个节点的 next 指向全部反过来，返回反转后的新头。例如输入 1→2→3→4→5→6→null，反转后应返回 6→5→4→3→2→1→null。题目要求原地完成、只用 O(1) 额外空间——这一条排除了「把所有值倒进数组再倒序重建一条链」的偷懒做法，逼你直接在原链表上改指针。

为什么不能上来就把指针掉头

单链表的致命约束是：想找到一个节点的后继，只能靠它的 next 指针，没有第二条路。假设当前站在节点 cur，直接把 cur.next 改成指向前面——后面那一整截链表就此失联，再也访问不到了。

这个约束反过来就把解法逼出来了：每一轮改指针之前，必须先用一个临时指针 next 把 cur 的后继保存下来。于是每轮固定三步——记住 next、把 cur.next 掉头指向 prev、prev 和 cur 双双右移一格。整个算法就是这三步的重复，没有任何别的分支。

循环维持的不变量是什么

任意一轮循环开始时都成立这样一个性质：prev 是「已反转部分」的头，从 prev 沿 next 走是一段方向已经掉转的链；cur 起往后是「未处理部分」，还保持原来的方向。两段合起来恰好覆盖所有节点，一个不丢。

每执行一轮上述三步，cur 这一个节点就从「未处理」搬进「已反转」，两段的分界线右移一格，性质原样保持。循环做 n 轮后未处理部分清空，整条链都掉转完毕——正确性不靠背模板，就靠这条不变量一路推到底。

为什么 prev 初始是 null、返回值也是 prev

prev 的初值必须是 null 而不是 head：原来的头节点反转后变成新链表的尾巴，尾巴的 next 应当指向 null。第一轮掉头时 cur.next = prev 恰好把原头指向 null，这个初值正好充当了新尾的终点，一行都不用特判。

循环条件是 cur 非空，退出时 cur 已经走到 null，prev 停在最后一个被处理的节点上——它就是反转后的新头，所以返回 prev 而不是 cur。误返回 cur 是这道题最常见的错误，那样返回值永远是 null。

复杂度怎么算，为什么首选迭代而不是递归

以上讲的正是参考代码采用的迭代解法。时间 O(n)：每个节点恰好被访问一次、改一次指针。空间 O(1)：全程只有 prev、cur、next 三个指针变量，不随链表长度增长。空链表也不用特判，循环一次都不执行，直接返回 null。

另一条路是递归：递到链表末端把最后一个节点当新头返回，回溯途中逐层把后继的 next 指回自己。思路优雅，但每层递归都占一个栈帧，空间是 O(n)，链表很长时还有栈溢出风险，所以迭代版是首选。这套「记后继、掉头、右移」的手法也是反转部分链表（LeetCode 92）和 K 个一组反转（LeetCode 25）的地基。

Python

def reverseList(head):
    prev = None
    cur = head
    while cur:
        nxt = cur.next      # 1) 记住下一个
        cur.next = prev     # 2) 掉头指向 prev
        prev = cur          # 3) prev 右移
        cur = nxt           #    cur 右移
    return prev             # prev 是新头

Java

public ListNode reverseList(ListNode head) {
    ListNode prev = null, cur = head;
    while (cur != null) {
        ListNode nxt = cur.next;  // 1) 记住下一个
        cur.next = prev;          // 2) 掉头
        prev = cur;               // 3) prev 右移
        cur = nxt;                //    cur 右移
    }
    return prev;
}

C++

ListNode* reverseList(ListNode* head) {
    ListNode *prev = nullptr, *cur = head;
    while (cur) {
        ListNode* nxt = cur->next;  // 1) 记住下一个
        cur->next = prev;           // 2) 掉头
        prev = cur;                 // 3) prev 右移
        cur = nxt;                  //    cur 右移
    }
    return prev;
}