K 个一组翻转链表
哪些公司问过
答案要点
- 先数够 k 个节点,不足 k 个直接保持原顺序返回
- 用 prev、curr、next 三指针反转这 k 个节点,先保存 next 防断链
- 反转后把本组头节点接到后续结果上,上一组尾节点接到本组新头
- 递归版空间 O(n/k),迭代版用 dummy 头节点空间 O(1),时间都是 O(n)
- 边界:k 为 1、链表为空、长度恰好是 k 的倍数
易错点
- 反转前没有先保存 next,导致断链
- 没有处理不足 k 个的尾部
- 组与组之间的指针接错
- 忘了使用 dummy 节点,头节点处理复杂
面试官常见追问
- 不足 k 个节点时为什么不反转?
- 如果不足 k 个也要反转,怎么改?
- 普通的链表反转怎么写?
- 迭代和递归哪个更好?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 链表的几种经典操作247 场
- 判断链表是否有环70 场
- 合并 K 个有序链表45 场
- Y 型链表找第一个相交节点21 场
- 链表反转及其变形20 场
- 链表重排(找中点、反转、合并)20 场
- 删除链表的倒数第 N 个节点15 场
- 链表排序:归并排序与快速排序9 场
- 链表每两个节点翻转8 场
- 旋转链表:向右移动 k 位8 场