LeetCode 25. K 个一组翻转链表 | C++ 迭代法最优解

📌 题目描述

题目级别：困难 (Hard)

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

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

进阶要求：你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换（即空间复杂度要求为 $O(1)$）。

---

💡 解题思路：分组模拟 + 迭代反转

这道题是“反转链表”的终极进阶版。核心思想可以拆解为三个步骤：先数数，再分组反转，最后重连首尾。

1. 统计节点总数

首先遍历一遍链表，统计出总节点数 n。这样我们就知道一共可以凑出多少个完整的 k 个一组，当 n < k 时，说明剩下的节点不够一组了，直接停止反转。

2. 引入虚拟头节点 (Dummy Node)

由于链表的头节点在反转后会发生改变，为了避免复杂的边界讨论，我们引入一个虚拟头节点 dummy，让 dummy->next = head。
同时定义一个指针 p0，它永远指向当前准备反转的这一组节点的前一个节点。初始时 p0 = dummy。

3. 组内反转与首尾重连（核心逻辑）

在每一轮反转中（条件是 n >= k），我们需要做两件事：

• 组内反转：使用标准的链表反转逻辑（pre, cur, ne），将这 k 个节点反转。
• 首尾重连：反转结束后，原本这组的第一个节点变成了最后一个节点，原本的最后一个节点变成了第一个节点。我们需要把它们与原链表重新缝合！

重连代码剖析：

ListNode* ne = p0->next; // p0->next 是这组原来的头，反转后它变成了尾部，我们用 ne 暂时存下来
p0->next->next = cur;    // 原来的头（现在的尾）需要指向下一组的开头（即反转结束后 cur 所在的位置）
p0->next = pre;          // p0（当前组的前驱节点）需要指向这组反转后的新头节点（即 pre）
p0 = ne;                 // p0 移动到当前组的尾部，作为下一组的前驱节点，继续下一轮！

💻 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 {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        // 1. 统计链表长度
        int n = 0;
        ListNode* cur = head;
        while (cur) {
            n++;
            cur = cur->next;
        }

        // 2. 初始化虚拟头节点和前驱指针 p0
        ListNode* dummy = new ListNode(-1, head);
        ListNode* p0 = dummy;
        ListNode* pre = nullptr;
        cur = p0->next; // cur 重新回到链表真实的头节点

        // 3. 只要剩下的节点够 k 个，就进行分组反转
        while (n >= k) {
            n -= k; // 扣除本轮的 k 个节点

            // --- 组内反转核心逻辑 ---
            for (int i = 0; i < k; i++) {
                ListNode* ne = cur->next;
                cur->next = pre;
                pre = cur;
                cur = ne;
            }

            // --- 首尾重连核心逻辑 ---
            ListNode* ne = p0->next; // 记录当前组最初的头节点（反转后变成当前组的尾节点）
            p0->next->next = cur;    // 将当前组的新尾节点连上后续未反转的链表
            p0->next = pre;          // 将当前组的前驱节点连上当前组的新头节点
            
            // 为下一组反转做准备
            p0 = ne;                 
        }

        return dummy->next;
    }
};