递归法代码讲解

在 NOI 竞赛中，处理这种“不确定数量”的链表输入通常有两种方式：一是使用 while(cin >> x) 配合 cin.get() 检查换行，二是先读取整行再用 stringstream 解析。为了保证代码的鲁棒性，我为你补全了包含快速 IO 优化、链表构建以及递归逻辑的完整 C++14 代码。

K 个一组翻转链表：递归版标准解答 (C++14)

#include <iostream>
#include <string>
#include <sstream>
#include <vector>

using namespace std;

// NOI 竞赛建议手动定义结构体，保持对内存的完全控制
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

/**
 * 辅助函数：反转区间 [a, b) 的节点
 * 关键点：这是一个左闭右开区间，b 是下一组的开头
 */
ListNode* reverseRange(ListNode* a, ListNode* b) {
    ListNode *prev = nullptr;
    ListNode *curr = a;
    ListNode *nxt = nullptr;
    while (curr != b) {
        nxt = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nxt;
    }
    // 返回反转后的新头节点（即原区间的最后一个节点 b 的前驱）
    return prev;
}

/**
 * 主递归函数：k 个一组翻转
 */
ListNode* reverseKGroup(ListNode* head, int k) {
    if (!head) return nullptr;
    
    // a 和 b 分别代表当前组的区间 [a, b)
    ListNode *a = head, *b = head;
    
    // 1. 探路逻辑：检查剩余节点是否足够 k 个
    for (int i = 0; i < k; i++) {
        // 易错点：如果在走完 k 步之前 b 变成了 nullptr
        // 说明剩余节点不足 k 个，根据题意需保持原样
        if (!b) return head; 
        b = b->next;
    }
    
    // 2. 递归分治：
    // 调用辅助函数反转当前这 k 个节点
    // 反转后，原先的头节点 a 变成了现在的尾节点
    ListNode* newHead = reverseRange(a, b);
    
    // 3. 衔接逻辑：
    // 当前组的尾部 (a) 应该接上 “后续所有组翻转后” 的结果
    // 下一组的起点正好是 b
    a->next = reverseKGroup(b, k);
    
    return newHead;
}

/**
 * 竞赛技巧：统一的输入处理与链表构造
 */
int main() {
    // 优化 1：加速输入输出 (NOI 常用)
    ios::sync_with_stdio(false);
    cin.tie(0);

    string line;
    if (!getline(cin, line)) return 0;
    
    stringstream ss(line);
    ListNode* dummy = new ListNode(0);
    ListNode* tail = dummy;
    int x;

    // 读入第一行：链表节点
    while (ss >> x) {
        tail->next = new ListNode(x);
        tail = tail->next;
    }

    // 读入第二行：k 的值
    int k;
    if (!(cin >> k)) k = 1;

    // 执行核心算法
    ListNode* resultHead = reverseKGroup(dummy->next, k);

    // 遍历输出结果
    ListNode* curr = resultHead;
    while (curr) {
        cout << curr->val << (curr->next ? " " : "");
        curr = curr->next;
    }
    cout << endl;

    // 提示：在 NOI 考场上，程序结束时可以不手动 delete 链表以节省时间
    // 操作系统会在进程退出时自动回收内存。
    return 0;
}

二、 深度解析与复杂度思考过程

1. 时间复杂度分析：$O(n)$

• 思考逻辑：
  • 我们通过 for 循环寻找 $k$ 个节点，相当于遍历一遍链表。
  • 在 reverseRange 函数中，每个节点执行了一次指针反转。
  • 总的来看，链表中的每一个节点都被“扫描”了常数次。
• 结论：时间复杂度为 $O(n)$。

2. 空间复杂度分析：$O(n/k)$

• 思考逻辑：
  • 本题采用了递归解法。递归的深度取决于分成了多少组。
  • 总节点数为 $n$，每组 $k$ 个，则递归调用栈的深度最大为 $n/k$。
• 优化建议：虽然 $O(n/k)$ 在 $n=5000$ 时完全没问题，但如果 $n$ 增加到 $10^6$ 且 $k=1$，递归会非常深。在那种极端情况下，**迭代法（使用 Dummy 节点和四个指针）**会将空间复杂度降至 $O(1)$，是更稳健的选择。

三、 考场避坑与易错点注释

1. 区间开闭问题： 在递归法中，使用 [a, b)（左闭右开）是最舒服的。a 指向当前组的第一个，b 指向下一组的第一个。这样在 reverseRange 时，循环条件 curr != b 能够完美处理 $k$ 个节点的反转。

2. “原头变现尾”： 递归归来时，最容易搞错的就是 a->next = ... 还是 newHead->next = ...。记住：a 是当前组反转前的头，反转后它在这一组的末尾，所以它是连接下一组的“挂钩”。

3. 不足 $k$ 个的特判： 这是题目中唯一一个可能导致逻辑分支错误的地方。必须先用 for 循环“探路”，一旦发现 !b 立即撤退（返回 head），不要等到反转到一半才发现不够。

4. $k=1$ 的情况： 虽然代码能运行，但在主函数加入 if (k <= 1) return head; 这种快速剪枝是优秀选手的职业习惯。

教练寄语： 递归法的精髓在于**“我相信这个函数能处理好剩下的事情”**。只要你写对了当前这 $k$ 个节点的反转逻辑，并把它们正确地接在递归调用的结果上，整个问题就迎刃而解了。这就是分治思想在链表中的完美体现！加油。

为了方便你创建 OJ 测试数据，我为你编写了一个基于 C++14 标准的数据生成器。

该生成器会生成 10 组测试点。由于本题的难点在于分组逻辑的余数处理以及大规模下的指针衔接，生成器特别构造了“恰好整除”、“余数极多”、“$k=1$”以及“$k=n$”等经典考点。生成器内部使用迭代逻辑生成标准答案，确保不会爆栈。

数据生成器代码 (gen_v3.cpp)

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <random>
#include <chrono>

using namespace std;

// 数据范围限制 (NOI 风格)
const int MAXN = 5000;
const int MAXVAL = 1000;

/**
 * 标准答案生成逻辑 (非递归迭代版)
 * 使用 vector 模拟链表反转，简单且 100% 准确
 */
void solve(const vector<int>& data, int k, string out_name) {
    ofstream fout(out_name);
    if (data.empty()) {
        fout << endl;
        return;
    }

    vector<int> res = data;
    int n = res.size();
    
    // 每 k 个一组进行反转
    for (int i = 0; i + k <= n; i += k) {
        reverse(res.begin() + i, res.begin() + i + k);
    }

    // 格式化输出
    for (int i = 0; i < n; ++i) {
        fout << res[i] << (i == n - 1 ? "" : " ");
    }
    fout << endl;
    fout.close();
}

/**
 * 写入输入文件 (.in)
 */
void write_input(const vector<int>& data, int k, string in_name) {
    ofstream fin(in_name);
    // 第一行：节点值
    for (int i = 0; i < (int)data.size(); ++i) {
        fin << data[i] << (i == (int)data.size() - 1 ? "" : " ");
    }
    fin << endl;
    // 第二行：k
    fin << k << endl;
    fin.close();
}

int main() {
    // 随机数发生器
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    uniform_int_distribution<int> val_dist(0, MAXVAL);

    for (int t = 1; t <= 10; ++t) {
        string in_name = to_string(t) + ".in";
        string out_name = to_string(t) + ".out";
        vector<int> data;
        int n = 0, k = 1;

        // 构造测试场景
        switch(t) {
            case 1: // 最小边界
                n = 1; k = 1;
                data.push_back(val_dist(rng));
                break;
            case 2: // k=1 (无任何变化)
                n = 100; k = 1;
                for(int i=1; i<=n; ++i) data.push_back(i);
                break;
            case 3: // k=n (全反转)
                n = 500; k = 500;
                for(int i=1; i<=n; ++i) data.push_back(i);
                break;
            case 4: // 恰好整除 (n=10, k=2)
                n = 10; k = 2;
                for(int i=1; i<=n; ++i) data.push_back(i);
                break;
            case 5: // 无法整除，保留末尾 (样例1)
                n = 5; k = 2;
                for(int i=1; i<=n; ++i) data.push_back(i);
                break;
            case 6: // 无法整除，保留末尾 (样例2)
                n = 5; k = 3;
                for(int i=1; i<=n; ++i) data.push_back(i);
                break;
            case 7: // 最大规模：k=2，频繁反转
                n = MAXN; k = 2;
                for(int i=1; i<=n; ++i) data.push_back(val_dist(rng));
                break;
            case 8: // 最大规模：k 很大，且留有余数
                n = MAXN; k = 4999;
                for(int i=1; i<=n; ++i) data.push_back(val_dist(rng));
                break;
            case 9: // 随机中规模
                n = 2000;
                k = uniform_int_distribution<int>(2, 500)(rng);
                for(int i=0; i<n; ++i) data.push_back(val_dist(rng));
                break;
            case 10: // 随机满规模
                n = MAXN;
                k = uniform_int_distribution<int>(1, MAXN)(rng);
                for(int i=0; i<n; ++i) data.push_back(val_dist(rng));
                break;
        }

        write_input(data, k, in_name);
        solve(data, k, out_name);
        
        cout << "Test Case " << t << " generated: n=" << n << ", k=" << k << endl;
    }

    return 0;
}

测试点详细说明表 (符合 OJ 评测需求)

数据生成器设计规范说明

1. 文件大小与效率：

   • 紧凑性：单组数据最大约为 25KB，10 组总计 250KB。这使得该数据集非常适合在带宽有限的评测环境下分发。
   • 生成耗时：由于 $n=5000$ 级别非常小，数据生成器在 0.1s 内即可完成全部文件的读写。

2. 安全性优化：

   • 避开除零：本题中 $k \ge 1$，生成器通过 uniform_int_distribution 强制 $k$ 的范围，消除了除以零或取模零的风险。
   • 栈安全：虽然 $n=5000$ 很难撑爆栈，但为了代码的通用性和严谨性，solve 函数采用了基于 std::vector 的迭代反转，即便 $n$ 扩充到 $10^6$ 也能平稳运行。

3. OJ 兼容性：

   • 输入流处理：输入的第一行是空格分隔的整数，这在后台评测时通过 while(cin >> x) 可以非常方便地读入。
   • 行末处理：生成器严格控制了每行末尾没有多余空格，且最后有且仅有一个换行符，避免因 PE (Presentation Error) 导致的不必要失分。

使用方法

1. 保存为 gen_v3.cpp。
2. 编译：g++ gen_v3.cpp -o gen -std=c++14。
3. 运行：./gen。
4. 生成的 *.in 和 *.out 即可打包上传至 OJ。

同学你好！“K 个一组翻转”是链表题中的巅峰之作。在 NOI 赛场上，如果遇到这种复杂的链表操作，我们通常有三种策略：从最稳妥的数组模拟，到逻辑优雅的递归，再到追求极致效率的迭代。

下面我们一步步拆解这道“困难”级别的题目。

版本一：数组/向量辅助法 (NOI 考场保底方案)

思路分析： 在竞赛中，如果内存限制允许（本题 $n=5000$ 极小），最不容易出错的方法是将链表节点先存入 std::vector。在数组中，翻转区间只需要 std::reverse。最后再根据数组顺序重建逻辑连接。

• 时间复杂度：$O(n)$，遍历两次。
• 空间复杂度：$O(n)$，使用了额外的数组存储节点指针。
• 评价：虽然不符合 LeetCode 原题的 $O(1)$ 空间要求，但在 NOI 考场上，这是最快写完且最不容易出错的拿分方案。

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* reverseKGroup(ListNode* head, int k) {
    if (!head || k == 1) return head;

    // 1. 将所有节点存入数组
    vector<ListNode*> nodes;
    while (head) {
        nodes.push_back(head);
        head = head->next;
    }

    int n = nodes.size();
    // 2. 分段翻转数组中的指针逻辑
    for (int i = 0; i + k <= n; i += k) {
        reverse(nodes.begin() + i, nodes.begin() + i + k);
    }

    // 3. 重新串联链表
    ListNode* dummy = new ListNode(0);
    ListNode* cur = dummy;
    for (int i = 0; i < n; i++) {
        cur->next = nodes[i];
        cur = cur->next;
    }
    cur->next = nullptr; // 关键：处理最后一个节点的 next，防止成环

    return dummy->next;
}

int main() {
    string line;
    getline(cin, line);
    stringstream ss(line);
    ListNode *dummy = new ListNode(0), *tail = dummy;
    int x, k;
    while (ss >> x) {
        tail->next = new ListNode(x);
        tail = tail->next;
    }
    cin >> k;

    ListNode* res = reverseKGroup(dummy->next, k);
    while (res) {
        cout << res->val << (res->next ? " " : "");
        res = res->next;
    }
    cout << endl;
    return 0;
}

版本二：递归法 (分治思想)

思路分析： 我们将问题看作：反转当前的 $k$ 个节点 + 递归处理剩下的节点。

1. 找到第 $k$ 个节点，如果不存在，直接返回头节点。
2. 反转前 $k$ 个节点（参考全链表反转）。
3. 让反转后的尾部（即原头节点）指向下一组递归的结果。

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(n/k)$，递归深度取决于分组数量。
• 关键点：递归是倒着接龙的，每一层只负责把自己的 $k$ 个节点转过来，然后接住后方的返回值。

见递归法代码专门讲解部分

版本三：迭代法 (最优复杂度 - $O(1)$ 空间)

思路分析： 这是最高级的写法。我们需要维护 pre（上一组的结尾）和 nextGroup（下一组的开始）。通过不断改变区间内的指针实现原地翻转。

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(1)$，仅使用若干指针。
• 易错点：指针连接的顺序。翻转后，必须把 pre->next 更新为新的组头，把翻转后的组尾连向下一组。

#include <iostream>
#include <string>
#include <sstream>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 工具函数：反转一个局部链表，并返回新的头和尾
// NOI 竞赛中建议使用 pair 返回，减少变量混乱
pair<ListNode*, ListNode*> myReverse(ListNode* head, ListNode* tail) {
    ListNode* prev = tail->next; // 初始指向下一组开头，方便连接
    ListNode* curr = head;
    while (prev != tail) {
        ListNode* nxt = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nxt;
    }
    return {tail, head}; // 返回 {新头, 新尾}
}

ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    ListNode* pre = dummy;

    while (head) {
        ListNode* tail = pre;
        // 1. 探路确认长度是否足够 k
        for (int i = 0; i < k; ++i) {
            tail = tail->next;
            if (!tail) return dummy->next;
        }
        
        ListNode* nxt = tail->next; // 暂存下一组起点
        
        // 2. 反转当前组
        pair<ListNode*, ListNode*> result = myReverse(head, tail);
        head = result.first;
        tail = result.second;

        // 3. 将反转后的片段接回原链表
        pre->next = head;
        tail->next = nxt;
        
        // 4. 移动指针，准备下一组
        pre = tail;
        head = nxt;
    }

    return dummy->next;
}

int main() {
    // 竞赛优化：读入加速
    ios::sync_with_stdio(false);
    cin.tie(0);

    string line;
    if (!getline(cin, line)) return 0;
    stringstream ss(line);
    ListNode *dummy = new ListNode(0), *tail = dummy;
    int x;
    while (ss >> x) {
        tail->next = new ListNode(x);
        tail = tail->next;
    }
    int k;
    if (!(cin >> k)) k = 1;

    ListNode* res = reverseKGroup(dummy->next, k);
    while (res) {
        cout << res->val << (res->next ? " " : "");
        res = res->next;
    }
    cout << endl;
    return 0;
}

七、 复杂度分析与建议

1. 时间复杂度分析思考：

   • 无论是哪种方法，每个节点被访问的次数都是常数级（探路 1 次，反转 1 次）。对于 $N=5000$，总操作数约 $10^4$，这在 1s 限制下绰绰有余（1s 通常可跑 $10^8$ 次运算）。

2. 空间复杂度优化建议：

   • 栈空间溢出：在 NOI 考场上，若 $N$ 很大（如 $10^6$），递归法（版本二）会面临 Runtime Error。对于这种结构明确的分组题目，**迭代法（版本三）**是专业选手的首选。
   • 内存池（Static Allocation）：竞赛中频繁 new 可能导致时间稍慢。可以预分配：ListNode pool[5005]; 来提升速度。

3. 读题关键词与坑点：

   • “不足 $k$ 个保持原序”：这是最容易漏掉的条件。在动手翻转前，必须先用一个循环走 $k$ 步试试，走不通就直接收工。
   • “$k=1$”：虽然代码通常能兼容，但在开始前特判 if (k == 1) return head; 可以减少逻辑复杂度并微弱提升速度。

教练寄语： 同学，恭喜你完成了链表反转的“全家桶”练习。这道题是考查你对局部逻辑封装能力的最好机会。在写这种复杂指针题时，给关键指针起好名字（如 pre, groupHead, groupTail, nextHead）比什么都重要！不要只用 p1, p2, p3，那会让你在调试时陷入混乱。继续加油！