☆打卡算法☆LeetCode 25、 K 个一组翻转链表 算法解析
☆打卡算法☆LeetCode 25、 K 个一组翻转链表 算法解析
恬静的小魔龙
发布于 2022-08-07 09:55:44
发布于 2022-08-07 09:55:44
一、题目
1、算法题目
“将给定的链表，每 k 个节点翻转一次，返回翻转后的链表。”
题目链接：
来源：力扣（LeetCode）
链接：25. K 个一组翻转链表 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
进阶：
- 你可以设计一个只使用常数额外空间的算法来解决此问题吗？
- 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
image.png
示例 1：
输入： head = [1,2,3,4,5], k = 2
输出： [2,1,4,3,5]
image.png
示例 2：
输入： head = [1,2,3,4,5], k = 3
输出： [3,2,1,4,5]二、解题
1、思路分析
这个题需要考虑的细节很多，首先需要把链表节点按照 k 进行分组，然后使用指针依次指向每组的头结点，每次判断每组的长度是否大于 k，是的话翻转这组链表，否则不需要。
还需要使用两个变量，pre和end用来指向待翻转链表的头和尾，在经过k次循环后，end到达末尾，记录待翻转的链表next=end.next，翻转链表后，重置pre和end，进行下一次循环。
2、代码实现
代码参考：
public class Solution {
public ListNode ReverseKGroup(ListNode head, int k) {
List<ListNode> list = new List<ListNode>();
ListNode p = head;
for (int i = 0; i < k; i++)
{
if (head == null) { return p; }
list.Add(head);
head = head.next;
}
for (int i = 1; i < k; i++)
{
list[i].next = list[i - 1];
}
list[0].next = ReverseKGroup(head, k);
return list[k - 1];
}
}
image.png
3、时间复杂度
时间复杂度 ： O(n)
其中n是链表的长度。
空间复杂度： O(1)
只需要建立常数个变量。
三、总结
有一个特殊情况需要注意，当翻转长度不够k时，定位到end完成后，end==null，说明已经到达链表末尾。
此时需要直接返回。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021-10-25，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录