LeetCode 25. K 个一组翻转链表

在链表类题目中，LeetCode 25. K 个一组翻转链表（Reverse Nodes in k-Group） 常被称为“Hard 守门员”。许多人在面试时容易写出 Bug，大多是因为把指针判断、分组遍历和局部反转全揉在一个循环里，导致指针丢失或成环。

其实只要掌握 虚拟头节点（Dummy Head） 与 模块化拆分（分治思想），这道题的逻辑就会变得无比清晰。

核心思考：4 个关键指针

在处理每一组长度为 k 的链表段时，我们只需锁定 4 个角色指针：

• groupPrev：指向待处理组的前驱节点（上一组翻转后的尾节点）。
• start：待处理组的起始节点（翻转后将变为当前组的尾部）。
• end：待处理组的末尾节点（翻转后将变为当前组的头部）。
• nextGroup：下一组的起始节点（提前记录，防止断链后丢失）。

指针操作的推演过程

处理每个分组的过程可以规范化为 5 个标准步骤：

1. 虚拟头节点起步：声明 ListNode dummy(0); dummy.next = head;，并初始化 groupPrev = &dummy[cite: 2]。这样能将“链表头部变化”与“中间节点变化”统一处理，省去所有头节点特判。
2. 探测并截取 $k$ 个节点：让 end 从 groupPrev 出发向前走 k 步。若中途遇到 nullptr，说明剩余节点不足 k 个，按题意保持原样，直接退出并返回。
3. 记录边界与彻底断链：
   • 记录 start = groupPrev->next;
   • 记录 nextGroup = end->next;
   • 斩断连接：执行 end->next = nullptr;。将待翻转段变成一个以 nullptr 结尾的独立单链表。
4. 子区间翻转：直接复用 LeetCode 206 基础的单链表反转函数 reverseList(start)。翻转完成后，原本的 end 成为新头节点，原本的 start 成为新尾节点。
5. 缝合两端并准备下一轮：
   • groupPrev->next = end; （前驱接新头）
   • start->next = nextGroup; （新尾接后继）
   • groupPrev = start; （groupPrev 前移到当前组尾部，处理下一组）

---

完整 C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
private:
    // 复用 LC 206 单链表反转
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr != nullptr) {
            ListNode* nextNode = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextNode;
        }
        return prev;
    }

public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (head == nullptr || k <= 1) return head;

        ListNode dummy(0);
        dummy.next = head;
        ListNode* groupPrev = &dummy;

        while (true) {
            // 1. 探测当前组是否凑齐 k 个节点
            ListNode* end = groupPrev;
            for (int i = 0; i < k; ++i) {
                end = end->next;
                if (end == nullptr) {
                    return dummy.next; // 不足 k 个，保持原样返回
                }
            }

            // 2. 记录前后边界并断开连接
            ListNode* start = groupPrev->next;
            ListNode* nextGroup = end->next;
            end->next = nullptr; // 断链，独立成标准子链表

            // 3. 翻转子链表
            reverseList(start);

            // 4. 缝合链表：前驱连新头(end)，新尾(start)连后继
            groupPrev->next = end;
            start->next = nextGroup;

            // 5. 步进指针，进入下一组
            groupPrev = start;
        }

        return dummy.next;
    }
};