LeetCode 25. K 个一组翻转链表 reverse N 核心思路

以下是精简核心版代码，仅保留性能关键逻辑，注释全覆盖核心步骤：

#include <iostream>
using namespace std;

// 链表节点定义
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:
    // ===================== 核心 1：翻转前 n 个节点（__reverseN）=====================
    ListNode* __reverseN(ListNode* head, int n) {
        // 终止条件：n=1，返回当前头（翻转后新头）
        if (n == 1) return head;
        // tail：原分组头，翻转后是分组尾节点
        ListNode* tail = head->next;
        // 递归翻转剩余 n-1 个节点
        ListNode* newHead = __reverseN(head->next, n-1);
        // 拼接节点：尾节点指向当前头
        tail->next = head;
        head->next = nullptr;
        return newHead;
    }

    // ===================== 核心 2：判断是否有 n 个节点（reverseN 判断）=====================
    ListNode* hasNNode(ListNode* head, int n) {
        ListNode* p = head;
        // 向后数 n 个节点
        while (n-- && p) {
            p = p->next;
        }
        // p 非空=有 n 个节点，返回 p；空=不足 n 个，返回 nullptr
        return p;
    }

    // ===================== 主函数：K 个一组翻转 =====================
    ListNode* reverseKGroup(ListNode* head, int k) {
        // 虚拟头节点（解决头节点翻转边界）
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        // p：待翻转区前驱；q：待翻转区头节点
        ListNode* p = dummy;
        ListNode* q = p->next;
        // 循环：有 k 个节点则翻转，否则终止
        while (hasNNode(q, k)) {
            // 翻转 q 开头的 k 个节点，得到新头
            ListNode* newHead = __reverseN(q, k);
            // 前驱节点拼接新头
            p->next = newHead;
            // 指针后移：p=当前分组尾，q=下一组头
            p = q;
            q = p->next;
        }
        // 返回最终链表头（虚拟头的 next）
        return dummy->next;
    }
};

调试实战：踩坑与修复（返回值核心问题）

在编写代码时，返回值错误是最常见的 bug，结合题目要求复盘调试过程：

1. 初始错误

问题：最初直接返回 head（原链表头节点），导致结果错乱； 原因：分组翻转后，原链表头节点变成了第一组的尾节点，不再是整个链表的头。

2. 修复方案

返回虚拟头节点的 next：return dummy->next，无论头节点如何翻转，虚拟头始终指向链表真正的头。

3. 翻转判断逻辑

题目指定关键判断： if (p->next != q) → 说明发生了翻转； if (p->next == q) → 说明未翻转（不足 k 个节点）。 该判断用于验证分组是否成功翻转，是调试的核心依据。

复杂度分析

1. 时间复杂度：O(n) 每个节点仅被遍历一次（计数一次 + 翻转一次），无嵌套循环；
2. 空间复杂度：O(k) 递归调用栈深度为 k（分组长度），若改用迭代版 __reverseN，空间可优化为 O(1)。

总结与技巧提炼

1. 核心思想：大问题拆小 → 用 reverseN 做计数校验，__reverseN 做单组翻转；
2. 必用技巧：虚拟头节点解决链表头变化的边界问题；
3. 指针关键：p 记录前驱，q 记录分组头尾，保证链表不断裂；
4. 终止条件：剩余节点不足 k 个时，直接终止循环，不做任何操作。

这道题是链表递归 + 迭代的综合运用，吃透「reverse N」思路，所有链表分段翻转类题目都能迎刃而解！