出现 537 次的唯一 Hard：难在一根指针上

高频榜前十名里只有一道 Hard：K 个一组翻转链表，出现 537 次，排第 5。

但这题有个很迷惑人的特点——它的思路一句话就能说完。

把链表每 k 个切成一组，组内反转，再把各组接起来。讲完。你在面试里花 15 秒就能把这个方案讲给面试官听，然后开始写，然后大概率写崩。

我拿三种"看起来很合理"的写法做了穷举搜索，想找出每种写法最早在哪个输入上出错。结果挺有意思：其中一种错误写法，节点一个没丢、一个没多、长度完全正确，只有逐位比对序列才能发现它是错的。

这题考的根本不是你想不想得到方案，是你敢不敢在动了第一根指针之后，还记得其余五根在哪。

一、先把正解写出来

public ListNode reverseKGroup(ListNode head, int k) {
   
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode prevGroup = dummy;

    while (prevGroup.next != null) {
   
        ListNode kth = prevGroup;
        for (int i = 0; i < k && kth != null; i++) kth = kth.next;
        if (kth == null) break;                       // 不足 k 个，保持原序

        ListNode groupNext = kth.next;                // 本组的后继，反转的终止哨兵
        ListNode prev = groupNext, cur = prevGroup.next;   // ★ prev 初值是 groupNext，不是 null
        while (cur != groupNext) {
   
            ListNode nxt = cur.next;
            cur.next = prev;
            prev = cur;
            cur = nxt;
        }
        ListNode oldFirst = prevGroup.next;           // 原组头，反转后变成组尾
        prevGroup.next = kth;                         // 前驱接上新组头
        prevGroup = oldFirst;                         // ★ 游标移到组尾，不是 kth
    }
    return dummy.next;
}

二十来行，里面标了两个 ★。这两个星号加上 break 那一行，就是这题的全部难点。

二、逐帧看一遍：一组要经过六次指针交接

用 [1,2,3,4,5]、k=2 走一遍，把每一帧的 prev、cur、nxt 和链表当时的真实形态都记下来：

看第 3 帧有个细节值得单独说：节点 2 从 dummy 出发已经走不到了，它只被 cur 指着。

这就是为什么代码里必须先 ListNode nxt = cur.next; 再改 cur.next = prev;。一旦先改了 cur.next，后半段链表就只能靠你事先存下的那个引用找回来了——顺序写反，链表当场断掉，而且断得很安静。

再看最后两帧。第二组接回后链表是 2→1→4→3→5，游标停在节点 3（原组头，现组尾）。下一轮从它出发走 2 步：3→5→null，撞到 null，于是 break，剩下的 5 保持原序。

"不足 k 个保持原序"这条规则，就是靠这个 break 实现的。 它看着最不起眼，但漏掉它的代码在 LeetCode 上会直接判错——见下一节 bug3。

三、三种典型错误，和它们各自的最小反例

我把三个最容易写错的地方各做成一个 bug 版本，然后让程序在 len ≤ 8 的全排列空间里穷举搜索，找每种错误最早暴露的输入。

三个 bug 的失败形态完全不同：

bug1 是断链。prev 初值是 null，第一组反转完，原组头节点 1 指向了 null，节点 3 从此失联。输出只剩两个节点。这个错误最"良心"，因为它会体现在长度上。

bug2 最阴。游标本该移到"组尾"（也就是原组头 oldFirst），写成 kth 就移到了"组头"。下一轮从这个位置再走 k 步，取到的区间和上一组重叠了。结果 [1,2,3] 变成 [2,3,1]——三个节点全在，一个不多一个不少，只是顺序不对。

bug3 是语义错。末组只有两个节点，硬反转成 [5,4]。节点也全在。

于是有个很不舒服的结论：bug2 和 bug3 都能通过"数一下长度对不对"和"元素齐不齐"这两种自查。 一个节点没丢、没重复，值的多重集完全守恒。你在面试里手写完，快速扫一眼"嗯，1 2 3 4 5 都在"，就放过去了。

唯一能抓住它们的，是逐位比对序列。

四、所以链表题应该怎么自查

我自己写验证程序时的做法，是拿一个笨到不可能错的参考实现做基准：先把值全部取进数组，按题意在数组里重排（够 k 个就反转这一段，不够就原样留着），再照着新数组重建一条链表。

这个参考实现的时间空间都很差，但它的正确性一眼可见。然后给它配三重检查，按代价从低到高排：

1) 节点数守恒   —— 从 head 走，步数超过原长即判定成环；步数不足即判定丢节点
2) 值多重集一致 —— 排序后比对，抓重复节点和丢节点
3) 逐位序列比对 —— 与参考实现的结果逐个比

第 1 重检查必须写成"步数上限"而不是"走到 null 为止"。因为断链重连的另一端失败形态是成环，while (cur != null) 会永远走不完。我在写 bug2 的搜索时专门加了步数上限保护，就是防这个。

穷举 + 随机的结果：

穷举组合=300（长度 0..9 × k 1..10 × 三种数据形态，迭代/递归各跑一遍）不一致=0
随机用例=50000（长度 0..59，k 1..12）新增不一致=0

面试时你没法跑测试，但这三重检查对应的自查动作是可以手做的，而且很便宜：

• 拿 [1,2,3,4,5] k=2 心算一遍，答案是 2→1→4→3→5。这是 LeetCode 官方第一个用例，也是能同时暴露三个 bug 的最小输入。
• 拿 k=1 自检。每组一个节点，反转是恒等操作，答案必须等于原链表。如果你的代码在 k=1 时结果变了，说明组的边界算错了。
• 拿 k 大于长度自检。一个节点都不该动。

这三个用例覆盖掉了这题所有的失败分支，成本是三十秒。

五、三种写法，和一个我亲自中的 off-by-one

迭代版是面试首选，O(1) 额外空间。

递归版更短，把"接回下一组"这件事交给返回值：

public ListNode reverseKGroupRec(ListNode head, int k) {
   
    ListNode kth = head;
    for (int i = 1; i < k && kth != null; i++) kth = kth.next;   // 注意是 i = 1
    if (kth == null) return head;
    ListNode groupNext = kth.next, prev = groupNext, cur = head;
    while (cur != groupNext) {
    ListNode nx = cur.next; cur.next = prev; prev = cur; cur = nx; }
    head.next = reverseKGroupRec(groupNext, k);   // 原组头（现组尾）接下一组的结果
    return kth;                                   // 新组头
}

这里有个我自己真的中过的坑。 迭代版里找第 k 个节点是 kth = prevGroup 然后走 k 步，因为 prevGroup 在组外面；递归版里起点是 head，它已经是组内第 1 个了，只能走 k−1 步。

我写递归版时直接照抄了 for (i = 0; i < k; i++)，结果 kth 落到了下一组的第一个节点上。穷举测试跑第一遍就报了一片：len=2, k=1 期望 [1,2] 实际 [2,1]——k=1 时它把整条链表反转了。

两版混着抄，是最容易中的毒。 面试官让你"再给一个递归写法"，考的往往不是你会不会递归，是你有没有注意到起点变了、步数也得跟着变。

递归版另一个追问点是空间：深度是 n/k。n=10⁵、k=2 时递归 5 万层，Java 默认栈是可能 StackOverflow 的。面试官问"能不能不用递归"，就是在等这句。

值回填法——把值取进数组、重排、写回原节点——在 LeetCode 上能 AC。但它经不起追问：如果节点挂着大对象、或者题目要求"真正移动节点"，这个写法直接出局。它能过，只是因为这道题恰好只关心值的顺序。用之前先想清楚这一点，别默认它是最优解。

六、这题的追问清单

金句：链表题的难，从来不在"想到怎么做"，而在"改了指针之后，你还记得有几个节点已经不属于原来的位置了"。

下一篇想写排名第 3 的 反转链表，出现 758 次。它是这十道里唯一标着 Easy 的，七行代码，看起来最没得可讲。但它是前十名里唯一一道递归版和迭代版复杂度不同的题——而且面试官真正想问的那句，是"递归返回的时候，栈上每一层的 head 分别指向谁"。

本文代码与配图由作者用华为云码道（CodeArts 代码智能体）辅助完成，三种写法与三个错误版本均经穷举与随机对撞验证。