IT 面试题库

编程题:K 个一组翻转链表(LeetCode 25):每 k 个节点一组进行翻转,不足 k 个保持原序,返回翻转后的头节点。请说明为什么这道题是「反转链表 + 合并有序结构」两道基础题的综合应用。

高级编程题算法工程师Java后端工程师链表分组反转LeetCode25边界处理

题目

考察点:把前两题的子能力(局部反转、拼接)组合成复杂操作,考查边界处理。追问:如何 O(1) 空间判断「这一组是否凑满 k 个」?

参考答案

内容深度:适中 · 无代码示例 · 来源:外部链接 · 未复核 · 72 天前更新 · 技术内容可能随版本变化,建议结合官方文档理解

要点:分三步——探边界、组内反转、组间缝合,本质是反复调用「反转一段链表」。

1. 用 dummy 挂头,groupPrev 指向每组前驱;

2. 从 groupPrev 出发探查 k 步,若不足 k 个直接结束(不足组保持原序);

3. 记录 groupEnd 与 groupNext,断开后对组内做标准反转(LeetCode 206 的迭代法),再把 groupPrev.next = 新头、原头.next = groupNext 缝回去;

4. groupPrev 移动到原组头(反转后的组尾),进入下一组。

练这道题

同分类 · 高频题

题目与答案就在本页;收藏、批注和错题重练在应用内

这道题看完了?连刷同类题,趁热打铁效果最好 进入刷题