链表反转中最常用的方法————三指针法

🎯 三指针法：链表反转的“瑞士军刀”

三指针法是解决单向链表反转问题的标准解法，无论是：

• 反转整个链表
• 反转部分链表（如第 m 到 n 个节点）
• K 个一组反转链表

它都适用，且逻辑清晰、不易出错。

🔧 核心思想

我们用 三个指针 来协作完成反转：

🔄 目标：让每个 curr 的 next 指向 prev，然后一起向前推进。

📈 动态过程图解（以反转前 3 个节点为例）

原始链表：

p -> A -> B -> C -> D -> ...
     ↑
   curr

我们想从 A 开始反转 k=3 个节点。

初始化：

ListNode prev = null;
ListNode curr = p.next;  // 即 A

此时：

prev = null
curr = A -> B -> C -> ...

🔁 循环执行 k 次：每次做 3 步操作

✅ 第 1 步：保存下一个节点

ListNode next = curr.next;

防止 curr.next 被修改后找不到后续节点。

prev = null
curr = A    next = B
       ↓
       B -> C -> ...

✅ 第 2 步：反转当前节点的指针

curr.next = prev;

把 A 指向 prev（即 null），完成第一个节点的反转。

prev = null <- A    next = B
                ↑
              curr

✅ 第 3 步：三个指针整体前移

prev = curr;  // prev 移到 A
curr = next;  // curr 移到 B

现在：

prev = A <- A    curr = B -> C -> ...
      ↑
    已反转部分

🔁 继续第二轮（处理 B）

next = curr.next;     // next = C
curr.next = prev;     // B -> A
prev = curr;          // prev = B
curr = next;          // curr = C

结果：

null <- A <- B    C -> ...
           ↑    ↑
         prev  curr

🔁 第三轮（处理 C）

next = curr.next;     // next = D
curr.next = prev;     // C -> B
prev = curr;          // prev = C
curr = next;          // curr = D

结果：

null <- A <- B <- C    D -> ...
                 ↑    ↑
               prev  curr

✅ 反转完成！

此时：

• prev 指向新的头节点（原来的第 k 个节点，即 C）
• curr 指向下一组的开始（即 D）
• 原来的第一个节点 A 现在是尾节点

🔗 最后连接前后

// 找到原段的尾节点（即反转前的头，现在是 p.next）
ListNode tail = p.next;

// 尾节点指向下一组开头
tail.next = curr;  // A.next = D

// p 指向新的头（即 prev）
p.next = prev;     // p -> C -> B -> A -> D -> ...

最终结构：

p -> C -> B -> A -> D -> ...

完美完成 k=3 的反转！

✅ 完整 Java 代码模板

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode p = dummy;

    while (p.next != null) {
        // 检查后面是否有 k 个节点
        ListNode curr = p.next;
        for (int i = 0; i < k; i++) {
            if (curr == null) return dummy.next;
            curr = curr.next;
        }

        // 开始反转 k 个节点
        ListNode prev = null;
        curr = p.next;

        for (int i = 0; i < k; i++) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        // 连接反转后的部分
        ListNode tail = p.next;  // 原来的头，现在的尾
        tail.next = curr;        // 指向下一段
        p.next = prev;           // p 指向新的头

        // p 移动到新尾部（即 tail）
        p = tail;
    }

    return dummy.next;
}

✅ 三指针法的优点

❗ 常见错误提醒

• ❌ 忘记保存 next → 断链，丢失后续节点
• ❌ 顺序写错：先改 curr.next 再保存 next
• ❌ prev 初始不是 null → 反转后成环
• ❌ 忘记最后连接 tail.next = curr

🎁 小技巧：记住口诀

“一保存，二反转，三前进”

1. 保存 next
2. 反转 curr.next = prev
3. prev = curr; curr = next;