链表反转：三种场景的模板

反转链表的核心操作

每次反转的单元是「让 cur.next 指向 prev」：

before: prev → cur → next → ...
after:  prev ← cur   next → ...

整表反转（LeetCode 206）

迭代（推荐）

ListNode reverseList(ListNode head) {
    ListNode prev = null, cur = head;
    while (cur != null) {
        ListNode next = cur.next;   // 保存后继
        cur.next = prev;            // 反转指针
        prev = cur;                 // 向前推进
        cur = next;
    }
    return prev;   // 新头节点
}

{
  "type": "linked-list",
  "title": "反转链表 1→2→3→4→5",
  "steps": [
    {
      "note": "初始：prev=null，cur=1",
      "listNodes": [
        {"id": 0, "val": 1, "next": 1},
        {"id": 1, "val": 2, "next": 2},
        {"id": 2, "val": 3, "next": 3},
        {"id": 3, "val": 4, "next": 4},
        {"id": 4, "val": 5, "next": null}
      ],
      "activeNode": 0
    },
    {
      "note": "1.next = null（反转），prev=1，cur=2",
      "listNodes": [
        {"id": 0, "val": 1, "next": null},
        {"id": 1, "val": 2, "next": 2},
        {"id": 2, "val": 3, "next": 3},
        {"id": 3, "val": 4, "next": 4},
        {"id": 4, "val": 5, "next": null}
      ],
      "activeNode": 1
    },
    {
      "note": "2.next = 1（反转），prev=2，cur=3",
      "listNodes": [
        {"id": 0, "val": 1, "next": null},
        {"id": 1, "val": 2, "next": 0},
        {"id": 2, "val": 3, "next": 3},
        {"id": 3, "val": 4, "next": 4},
        {"id": 4, "val": 5, "next": null}
      ],
      "activeNode": 2
    },
    {
      "note": "3.next=2，4.next=3，5.next=4。完成，头节点=5",
      "listNodes": [
        {"id": 0, "val": 1, "next": null},
        {"id": 1, "val": 2, "next": 0},
        {"id": 2, "val": 3, "next": 1},
        {"id": 3, "val": 4, "next": 2},
        {"id": 4, "val": 5, "next": 3}
      ],
      "activeNode": 4
    }
  ]
}

递归（理解递归思维）

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;
}

递归逆序调用，相当于从末尾开始反转，依次向前传播。

反转前 N 个节点

ListNode successor;  // 记录第 N+1 个节点

ListNode reverseN(ListNode head, int n) {
    if (n == 1) {
        successor = head.next;   // 第 N+1 个节点
        return head;
    }
    ListNode newHead = reverseN(head.next, n - 1);
    head.next.next = head;
    head.next = successor;   // 连接到后续部分
    return newHead;
}

反转区间 [left, right]（LeetCode 92）

找到第 left-1 个节点，对其后的 right-left+1 个节点做反转，再重连：

ListNode reverseBetween(ListNode head, int left, int right) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode pre = dummy;

    // 走到 left-1
    for (int i = 1; i < left; i++) pre = pre.next;

    // 头插法反转 right-left+1 个节点
    ListNode cur = pre.next;
    for (int i = 0; i < right - left; i++) {
        ListNode next = cur.next;
        cur.next = next.next;
        next.next = pre.next;
        pre.next = next;
    }
    return dummy.next;
}

头插法是反转区间的常用技巧：每次把 cur.next 摘出来插到 pre.next，不需要额外的 prev 指针。

K 个一组翻转链表（LeetCode 25）

先看后面够不够 k 个，够就反转，不够就保持原样：

ListNode reverseKGroup(ListNode head, int k) {
    // 检查是否有 k 个节点
    ListNode tail = head;
    for (int i = 0; i < k; i++) {
        if (tail == null) return head;   // 不足 k 个，原样返回
        tail = tail.next;
    }
    // 反转这 k 个节点
    ListNode newHead = reverse(head, tail);
    // 递归处理后续部分
    head.next = reverseKGroup(tail, k);
    return newHead;
}

// 反转 [head, tail) 区间内的节点
ListNode reverse(ListNode head, ListNode tail) {
    ListNode prev = null, cur = head;
    while (cur != tail) {
        ListNode next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

总结