题干与适用场景
给定单链表头节点 head 和正整数 k。从头开始，把每个完整的连续 k 节点分组原地反转； 如果末尾剩余节点少于 k，保持它们的原有顺序。只能重连节点，不能通过交换 value 伪装成节点反转。
例如，1 → 2 → 3 → 4 → 5 在 k = 2 时变成 2 → 1 → 4 → 3 → 5；在 k = 3 时变成 3 → 2 → 1 → 4 → 5。假设 1 ≤ k ≤ n ≤ 5000，输入无环，目标是 O(n) 时间和 O(1) 额外空间。
这道题适合算法工程、后端、基础架构及通用软件工程的编码面试。难点不在“会不会反转链表”，而在能否先确认 完整分组、保住下一组入口、正确接回前缀与后缀，并说明为什么不会丢节点或形成环。
面试官考察点
第一，能否把问题拆成定位边界、反转区间、重新连接三个动作。直接从当前节点开始反转，一旦走到不足 k 的尾部，就很难无额外存储地恢复原序。强答案会在修改任何指针前先向前检查 k 个节点。
第二，能否维护清楚的指针角色。groupPrev 位于当前组之前，kth 是完整组的最后一个节点， groupNext 是下一段入口，当前组原来的头在反转后会成为尾。每次循环结束后，前缀应已经完成且可达， groupPrev.next 应指向第一段尚未处理的节点。
第三，能否给出不变量而非只背代码。把 prev 初始化为 groupNext，可以让当前组原来的头在第一次被改写时 最终指向后缀；反转结束只需把前一段接到 kth，组内和后缀的连接已经成立。
第四，复杂度是否与实现一致。每个节点至多被完整组预检访问一次、被反转访问一次，所以总时间仍为 O(n)； 算法只保存固定数量的节点引用，额外空间为 O(1)。递归版本即使时间相同，也会使用与组数相关的调用栈。
回答前需要澄清的问题
- 最后不足
k个节点怎么处理？ 本题保持原序。有些变体会反转尾组，两者输出不同，必须先确定契约。 - 可以交换节点值吗？ 不可以；如果节点还带身份、外部引用或其他字段，换值并不等于重连节点。
k的合法范围是什么？ 本题保证1 ≤ k ≤ n。通用函数仍可对非整数或小于 1 的值明确报错。- 输入可能有环吗？ 本题假设无环。若可能有环，应先定义拒绝还是处理；否则预检与主循环可能永不结束。
- 是否必须原地完成？ 是。允许
O(k)空间时，栈方案更容易书写，但不满足本题目标。 - 节点对象能否复用？ 必须复用所有原节点；不能创建一条只复制值的新链表。
30 秒回答框架
“我会放一个指向 head 的哑节点，并让 groupPrev 指向当前组之前。每轮先从 groupPrev 向前走 k 步找到 kth；走不到就直接返回，因为这时还没有修改尾部。保存 groupNext = kth.next 后， 把 prev 初始化为 groupNext，再把当前组每个节点的 next 逐个反向。这样原组头会自动成为指向 groupNext 的新尾。最后令 groupPrev.next = kth，再把 groupPrev 移到原组头。每个节点最多经历 一次预检和一次反转，所以时间 O(n)、额外空间 O(1)。”
分步骤深入解答
先建立哑节点。第一组反转后链表头会变化；哑节点让“把前缀接到新组头”在第一组和后续组使用同一条语句， 避免单独处理头节点。
每轮必须先完成分组预检。从 groupPrev 出发恰好移动 k 次，得到 kth。如果途中到达 null， 剩余节点不足 k，立即返回 dummy.next。由于预检期间没有写指针，尾部自然保持原序。
实现如下：
class ListNode {
constructor(value, next = null) {
this.value = value
this.next = next
}
}
function reverseKGroup(head, k) {
if (!Number.isInteger(k) || k < 1) {
throw new RangeError('k must be a positive integer')
}
const dummy = new ListNode(0, head)
let groupPrev = dummy
while (true) {
let kth = groupPrev
for (let step = 0; step < k; step += 1) {
kth = kth.next
if (kth === null) {
return dummy.next
}
}
const groupNext = kth.next
let prev = groupNext
let current = groupPrev.next
while (current !== groupNext) {
const nextNode = current.next
current.next = prev
prev = current
current = nextNode
}
const oldGroupHead = groupPrev.next
groupPrev.next = kth
groupPrev = oldGroupHead
}
}以 1 → 2 → 3 → 4 → 5、k = 3 为例。预检得到 kth = 3，保存 groupNext = 4。 反转前令 prev = 4，然后依次改写 1.next = 4、2.next = 1、3.next = 2。此时 3 是新组头， 1 是新组尾且已连到 4。把哑节点接到 3，再把 groupPrev 移到 1。下一轮预检无法取得三个节点， 直接返回，4 → 5 没有被改动。
循环不变量可以写成三条：循环开始时，dummy.next 到 groupPrev 的前缀已按完整分组正确反转； groupPrev.next 是第一条未处理节点；所有未处理节点仍保持输入顺序且可达。预检失败不写指针，因此不变量直接 推出尾部保持原序。预检成功时，反转只改写当前 k 个节点，groupNext 保住后缀入口；重新连接后，已完成前缀 恰好多一组，不变量恢复。每轮处理 k 个新节点，最终必然终止。
复杂度方面，预检和反转各自最多触碰每个节点一次，总工作量不超过约 2n 次节点访问，因此为 O(n)， 不是 O(nk)。哑节点和指针数量不随输入增长，额外空间为 O(1)。
允许额外空间时，可以把一组节点压入栈再弹出，代码更直观但使用 O(k) 空间。递归方案可以先确认完整组、 反转后递归处理剩余部分，调用栈为 O(n / k)。在面试目标明确要求常量空间时，迭代方案更合适；若输入很小且 重点是快速交付一个易审查版本，栈方案也可以作为明确的第一版。
验证不能只比较值数组。应先保存原节点引用集合，运行后沿结果链表遍历：确认没有环、节点数量不变、引用集合 完全相同，再检查顺序。最少覆盖空链表的防御性用例、单节点、k = 1、n = k、n 能被 k 整除、尾部 不足 k、重复值和最大规模。重复值尤其能证明测试不能依赖节点值判断是否复用了原对象。
高质量示范回答
“我先确认尾部不足 k 个节点保持原序，而且不能交换值。我的迭代状态只有一个哑节点和几条引用。 groupPrev 始终指向当前组前一个节点；每轮从它向前走 k 步。如果找不到 kth，我会立刻返回， 因为尚未修改任何尾部指针。
找到完整组后，我保存 groupNext。反转时把 prev 初始化成 groupNext，然后从原组头走到 groupNext 之前，逐个执行标准三指针反转。这个初始化很关键：原组头变成尾时，它的 next 已经指向下一段。 反转完成后，kth 是新组头，我把 groupPrev.next 接到它，再把 groupPrev 移到原组头。
正确性依赖一个循环不变量：已处理前缀始终正确且连通，groupPrev.next 是第一条未处理节点，未处理后缀仍保持 输入顺序。完整组反转只扩大前缀；不足一组时没有写操作，所以尾部原序保留。每个节点最多被预检和反转各访问 一次，时间是 O(n)，额外空间是 O(1)。我会用节点身份和无环检查验证，而不只比较值。”
常见错误
- 未确认完整组就开始反转 → 尾部不足
k时已破坏原序且难以恢复 → 先只读预检，再写指针。 - 反转时令
prev = null→ 当前组会暂时与后缀断开，容易漏接 → 令prev = groupNext。 - 只连接新组头 → 原组头变成的新尾可能没有连到后缀 → 保留
groupNext，并检查新尾指向它。 - 反转后仍把
kth当作下一轮前驱 → 下一轮边界错误 → 把groupPrev移到原组头。 - 交换节点值 → 节点身份和附加字段语义被破坏 → 只修改
next。 - 声称递归额外空间为
O(1)→ 调用栈随组数增长 → 迭代版才满足常量额外空间。 - 只测值序列 → 丢节点、复制节点或成环可能被漏掉 → 同时检查引用集合、节点数和无环性。
- 把预检与反转相乘成
O(nk)→ 忽略每轮处理新的不相交分组 → 按每个节点的总访问次数求和。
追问及应对
追问一：如果最后不足 k 个节点也要反转呢？
契约变化后，预检失败不能直接返回。可以让预检同时得到实际剩余数量，并对这段剩余节点执行同样的区间反转； 或者先求链表长度，再令每轮组大小为 min(k, remaining)。需要重写不变量中的终止条件，并增加 n < k 的测试。
追问二：如何每隔一组才反转？
仍按完整 k 节点组预检，再维护布尔标记。需要反转的组执行原逻辑；跳过的组不改指针，只把 groupPrev 前移 k 次。尾部规则必须再次确认，因为“最后不足一组”是否算一个需要跳过或反转的组会改变结果。
追问三：如何证明没有形成环？
局部证明依赖两个边界：反转前保存不属于当前组的 groupNext；反转从 prev = groupNext 开始，并在 current === groupNext 时停止。每条被改写的边都从当前节点指向已处理的前驱或后缀入口，不会指回仍未处理的 当前组节点。测试层再使用快慢指针检查无环，并确认遍历节点数等于输入节点数。
追问四：如果链表有一亿个节点，方案需要改变吗？
渐进复杂度不变，但需要取消递归、避免复制节点，并评估单次长任务的超时和取消语义。若链表位于外部存储或跨机 分片，随机重连和原子可见性会成为主要问题，单机内存链表算法不能直接套用；这时应先重新定义数据布局、事务边界 和可恢复检查点。