MUYI · 后端工程师的生产级知识体系

Appearance

反转链表 ​

一、题目（LeetCode 206 · 简单 · Hot100） ​

给定单链表的头节点 head，反转链表，返回反转后的链表。

输入：head = 1 -> 2 -> 3 -> 4 -> 5
输出：5 -> 4 -> 3 -> 2 -> 1

进阶：链表可以选用迭代或递归方式完成，能否用 O(1) 空间迭代实现。

二、思路演进 ​

2.1 朴素：拿外部容器"装值重建" ​

遍历取值压栈（或数组），再顺序弹回各节点的 val——时间 O(n) 但额外 O(n) 空间。头插法新建一条链表同样是 O(n) 空间。能用，但面试官下一句必然是"O(1) 空间怎么做"，以及"只换 val 不换节点在哪些场景不合法"。节点被外部引用、节点还挂着业务数据时不能动 val，只能动指针。

2.2 关键洞察：反转只是"逐个掉头"的局部动作 ​

对每个节点而言，反转唯一要做的事是把 next 指向它的前驱。直接改指针会丢掉后继导致断链，解法是用三个指针完成一轮原子的"保存—掉头—平移"：

prev（已反转部分的头）  cur（待处理）  next（提前保存，防断链）

cur 走到 null 时，prev 恰好停在原链表的最后一个节点上——它就是新头。指针修改是 O(1) 的，这正是链表相对数组的结构性优势。同族指针题见 [环形链表 I](环形链表 I.md)、合并两个有序链表、[删除链表的倒数第 N 个结点](删除链表的倒数第 N 个结点.md)。

2.3 递归视角：先反转后面，再接自己 ​

reverse(head) 的定义是"返回以 head 开头反转后的新头"。先递归反转 head.next 之后的那段，拿到 newHead。再把 head.next.next = head（让后继反过来指向自己）、head.next = null（自己成为新尾）。优雅但栈深 O(n)，长链上会溢出，生产代码用迭代。

三、复杂度分析 ​

  • 迭代：时间 O(n)（cur 平移 n+1 次），空间 O(1)（三个指针）。
  • 递归：时间 O(n)，空间 O(n)（调用栈深度等于链长，10^5 节点足以 StackOverflow）。

四、代码 ​

java
package org.example;

/**
 * @author MUYI
 * @version 1.0
 * @date 2026/10/17
 */
public class LeetCode_206 {

    public static void main(String[] args) {
        ListNode head = build(new int[]{1, 2, 3, 4, 5});
        ListNode node = reverseList(head);
        while (node != null) {              // 期望输出 5 4 3 2 1
            System.out.print(node.val + " ");
            node = node.next;
        }
    }

    /** 迭代版：三指针原地掉头 */
    public static ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur  = head;
        while (cur != null) {
            ListNode next = cur.next;       // 先保存后继，改指针后才不断链
            cur.next = prev;                // 掉头：指向前驱
            prev = cur;                     // 已反转部分右扩一格
            cur = next;                     // 推进到下一个待处理节点
        }
        return prev;                        // cur == null 时 prev 即新头
    }

    /** 递归版：反转 head 之后，把 head 接到尾部 */
    public static ListNode reverseRecursive(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseRecursive(head.next);
        head.next.next = head;              // 原后继反过来指向自己
        head.next = null;                   // 自己变新尾，断开原方向防成环
        return newHead;
    }

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
    }

    static ListNode build(int[] values) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (int v : values) {
            tail.next = new ListNode(v);
            tail = tail.next;
        }
        return dummy.next;
    }

}

五、坑点 ​

  • 先存 next 再改 cur.next：两行顺序一反，改完指针后继就永远找不回来了。
  • 返回的是 prev 不是 cur：循环结束时 cur == null，prev 是最后一个被处理的节点（新头）。
  • 循环条件 cur != null：写成 cur.next != null 会漏掉最后一个节点的掉头。
  • 递归版漏 head.next = null：原头与新尾互指成环，遍历输出会死循环。
  • 空链表、单节点被通用逻辑天然覆盖（循环直接不进 / 进一轮），无需特判。但面试时要主动说"验证过这两个边界"。

六、变形追问 ​

  • 变体一（反转链表 II，LeetCode 92）：只反转区间 [left, right]。模板不变，难点变成接驳：进入区间前记住前驱，反转完把三段重新缝起来。哑结点同样是为了让 left=1 时无特判。
  • 变体二（K 个一组翻转，LeetCode 25，Hot100）：每组内调用本模板，组间做与变体一相同的接驳。追问点是"不足 k 个保持原样"的判定放在分组前做。

2026-10 新增（E 轨 · Hot100 第一批）。