type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
输入是链表的头节点
head ,每 k 个节点一组进行翻转,返回修改后的链表。说明:
k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是
k 的整数倍,那么请将最后剩余的节点保持原有顺序。不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。
示例 1:

示例 2:

解法一:双 / 三指针迭代(推荐)
这题的本质是:把链表按照 k 个一组进行切片,每一片翻转,然后再把这些片段按原顺序连接回去。
为了能优雅地处理开头和每段的拼接,一般都会创建一个 dummy 节点作为链表的起点。
核心逻辑是:
- 维护两指针
left 指向待反转段的前一个节点;right 用来定位反转段末的后一个节点(半开区间 (left, right))。- 当两者之间的有
k个节点时,进行区间反转:把(left, right)之间的链表就地反转。并返回新段的尾节点作为下一段的left。
- 再继续下一段。
复杂度
- 时间:O(n) 整段链表只会扫描一遍,每一段只翻转一次,因此整个过程是线性的。
- 空间:O(1) 只用常数级指针,不借助额外结构。
解法二:递归
- 先判断当前剩余的链表里,节点数量是否够 k 个
- 如果不够,就不需要翻转
- 如果够,用简单的 for 循环实现这 k 个节点的翻转
- 递归处理第
k+1个开始的后面部分的翻转
- 然后把两段拼在一起
复杂度
- 时间:O(n) 每段翻一次,整条链表只遍历一次。
- 空间:O(n/k)(递归栈)
- Author:Fan Luo
- URL:https://fanluo.me/article/leetcode-25-k-个一组翻转链表
- Copyright:All articles in this blog adopt BY-NC-SA agreement. Please indicate the source!
上一篇
[Leetcode 23] 合并 K 个升序链表
下一篇
[Leetcode 32] 最长有效括号