XingHuiSama の博客

给你链表的头节点 head ，每 k个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

示例 2：

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

提示：

链表中的节点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000

1. 算法核心思想：探路机制与区间独立重组

将链表按 K 个一组进行翻转，本质上是“链表局部反转”的进阶版。算法的核心挑战在于如何精准控制翻转的边界，以及如何在翻转后重新接回主链表。

采用了“探路者”模式：利用 cur 指针和一个计数器 d，每次固定向前试探 K 步。

如果凑齐了 K 个节点（d == 0），则截取这段区间交由辅助函数进行翻转。
如果不满足 K 个节点，则停止操作，保持原样。这种将“探测”与“翻转”逻辑严格解耦的设计，使得代码状态非常清晰，避免了在同一个循环中处理过多变量导致的混乱。

2. 逻辑拆解

特判与虚拟头节点：开头的 if (k == 1) 是非常实用的工程优化，避免了无意义的运算。引入虚拟头节点 p 则是为了让第一组的翻转与其他组的翻转享有相同的操作逻辑（都需要一个前驱节点 pre）。
状态机的重置与步进：外层通过 while (d == 0) 控制流程。每完成一次区间翻转，reverse1 函数会返回该区间反转后的尾节点。将其赋值给 pre 和 cur，即可作为下一个周期的起始锚点。随后重置计数器 d，继续向后探路。
独特的累加反转（reverse1 机制）：这是本解法最具特色的部分。传统的反转是将箭头依次向后掉头，而此解法利用 temp2 指针，初始指向下一区间的头部（cur->next）。在 while 循环中，从前往后遍历当前区间，将每个节点依次“挂”在 temp2 的前方。这一操作在建立逆序的同时，自然而然地完成了与后继链表的拼接。最后通过 pre->next = p 完成与前驱链表的拼接，实现了闭环。

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        // 特判优化：如果 k=1，相当于不翻转，直接返回
        if (k == 1) return head; 

        ListNode *p = new ListNode(0);
        p->next = head;
        ListNode *ans = p; // 记录虚拟头节点用于最终返回

        ListNode *cur = p, *pre = p;
        int d = k;

        // 1. 第一次探路：检查初始链表是否满足 k 个节点
        while (cur->next != NULL && d != 0) {
            cur = cur->next;
            d--;
        }

        // 2. 核心遍历：只要当前区间满足 k 个节点（d == 0），就执行翻转
        while (d == 0) {
            // 翻转当前区间，并返回翻转后的尾节点作为下一区间的 pre
            pre = reverse1(pre, cur);
            cur = pre; // 游标回退到新区间的起点
            d = k;

            // 再次探路，判断剩下的节点是否还够 k 个
            while (cur->next != NULL && d != 0) {
                cur = cur->next;
                d--;
            }
        }

        ListNode* ret = ans->next;
        delete ans; // 释放堆内存
        return ret;
    }

private:
    // 局部翻转辅助函数（头插法变体）
    ListNode* reverse1(ListNode* pre, ListNode* cur) {
        ListNode* p = pre->next;
        ListNode* temp;
        ListNode* ans = pre->next;   // 翻转后的尾节点，用于返回
        ListNode* temp2 = cur->next; // 提前记录下一区间的头部

        // 核心翻转逻辑：不断把当前节点接在 temp2 前面，实现逆序累加
        while (p != cur) {
            temp = p;
            p = p->next;
            temp->next = temp2;
            temp2 = temp;
        }

        // 处理区间最后一个节点，并重新与前驱节点连接
        p->next = temp;
        pre->next = p;

        return ans;
    }
};

3. 复杂度分析

时间复杂度：O(N)。其中 N 为链表的总节点数。每个节点最多被访问两次（一次被 cur 探路访问，一次在 reverse1 中被反转），整体耗时与数据规模呈线性关系。
空间复杂度：O(1)。算法主要依赖有限的几个游标指针（cur、pre、temp 等）进行原地状态修改，没有使用递归调用栈或额外的数据结构。