如何反转一个单链表？ - AIGC面试刷题网

简化版

用三个指针迭代：prev、cur、next。每一步先记住 cur.next，把 cur.next 指回 prev，再让 prev、cur 各往后挪一位，直到 cur 为空，此时 prev 就是新头。时间 O(n)、空间 O(1)。也能用递归实现。

详细版

迭代法（推荐，O(1) 空间）：核心是「边走边掉头」。

ListNode reverse(ListNode head) {
    ListNode prev = null, cur = head;
    while (cur != null) {
        ListNode next = cur.next; // 1. 先存住下一个，别丢
        cur.next = prev;          // 2. 当前节点掉头指向前驱
        prev = cur;               // 3. prev 前进
        cur = next;               // 4. cur 前进
    }
    return prev; // 原来的尾节点变成了新头
}

递归法：先反转后面的子链表，再把当前节点接到尾部。

ListNode reverse(ListNode head) {
    if (head == null || head.next == null) return head; // 空或单节点
    ListNode newHead = reverse(head.next); // 反转 head 之后的部分
    head.next.next = head;  // 让下一个节点指回自己
    head.next = null;       // 断开自己原来的指向，避免成环
    return newHead;         // 新头一直是最末节点
}

递归写起来短，但会用 O(n) 的调用栈，链表很长可能栈溢出；迭代 O(1) 空间更稳，面试首选迭代、能顺带说清递归即可。

完整版教学

一、为什么必须先存 `next`

反转的动作是 cur.next = prev，可这一步会覆盖掉 cur 原本指向的下一个节点。如果不提前用 next 把它存下来，链表后半段就断了、再也找不回来。所以顺序永远是：存下一个 → 掉头 → 双指针前进，四步一个都不能乱。

二、迭代过程走一遍

以 1 → 2 → 3 → null 为例，看每轮结束后的状态：

初始:            prev=null      cur=1→2→3
第1轮后: null←1   prev=1         cur=2→3
第2轮后: null←1←2 prev=2         cur=3
第3轮后: null←1←2←3 prev=3       cur=null → 结束
返回 prev=3，链表变成 3 → 2 → 1 → null

关键点：prev 始终指向「已经反转好的那段的头」，循环结束时它就是最终新头。

三、递归法的两个易错点

递归的思路是「假设 reverse(head.next) 已经把后面反转好了」，此时 head.next 是反转后子链表的尾节点，只要：

head.next.next = head：让那个尾节点指回 head，把 head 接到末尾；
head.next = null：把 head 原来的指向断掉。漏了这步会形成环（head 和 head.next 互相指），是最常见的 bug。

另外，newHead（最末节点）在整条递归里一路原样返回，最终传回给调用者。

四、复杂度与选择

迭代：时间 O(n)，空间 O(1)。
递归：时间 O(n)，空间 O(n)（递归调用栈）。

面试写迭代最稳；如果被追问「递归怎么写」再补递归，并主动指出它的栈空间和「断尾防成环」这两点，能体现你想得细。

五、延伸：反转部分链表 / K 个一组

很多进阶题（反转链表的 [m, n] 区间、每 K 个一组反转）都是在这套「三指针掉头」的基础上加边界处理，核心动作不变。掌握了基础反转，这些都是同一招的变体。

写法	时间	额外空间	面试建议
迭代三指针	O(n)	O(1)	首选，稳定且不怕长链表
递归	O(n)	O(n) 调用栈	代码短，但要说明栈空间和断尾
头插法	O(n)	O(1)	常用于局部反转、K 个一组反转

以长度 100000 的链表为例，迭代法只维护 prev/cur/next 三个引用；递归法会产生约 100000 层调用栈，在很多运行环境里可能触发栈溢出。所以工程或面试手写时，迭代法通常更稳。

反转链表最重要的顺序是“先保存 next，再改 cur.next”。只要这一步顺序反了，后半段链表就可能丢失。

六、常见误区与追问

误区：可以先 cur.next = prev 再找下一个节点。 一旦覆盖 cur.next，原来的后继就丢了，必须提前保存 next。
误区：递归法空间也是 O(1)。 递归没有显式数据结构，但调用栈会占 O(n) 空间。
误区：递归里不需要 head.next = null。 不断开原指向会形成环，例如 1 和 2 互相指。
追问：空链表和单节点怎么处理？ 迭代法自然返回 null 或原节点；递归法要把它们作为终止条件。
追问：如何反转链表的一段？ 核心仍是三指针反转，只是要记录区间前驱和区间后继，反转后再接回去。
追问：为什么返回 prev 而不是 cur？ 循环结束时 cur 已经是 null，prev 才指向反转后链表的新头。

七、加强记忆

反转单链表就是「三指针边走边掉头」：存下一个、当前掉头、双指针前进，循环结束时 prev 是新头。递归版记住「反转后半段 + 尾节点指回自己 + 自己断尾防成环」。迭代 O(1) 空间是首选。

简化版

详细版