【打卡算法】25、 K 个一组翻转链表 算法解析

恬静的小魔龙 发表于 2022/07/29 00:40:07 2022/07/29
【摘要】 推荐阅读 CSDN主页GitHub开源地址Unity3D插件分享简书地址我的个人博客QQ群:1040082875 大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不...

推荐阅读

大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。

一、题目

1、算法题目

“将给定的链表,每 k 个节点翻转一次,返回翻转后的链表。”

题目链接:

来源:力扣(LeetCode)

链接:25. K 个一组翻转链表 - 力扣(LeetCode) (leetcode-cn.com)

2、题目描述

给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。

k 是一个正整数,它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

进阶:

  • 你可以设计一个只使用常数额外空间的算法来解决此问题吗?
  • 你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NqXgq9Ag-1658998735700)(https://p9-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/fc291711256348c897c92c74d5a1412b~tplv-k3u1fbpfcp-watermark.image?)]

示例 1:
输入: head = [1,2,3,4,5], k = 2
输出: [2,1,4,3,5]

  
 
  • 1
  • 2
  • 3

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Q5O5XMyH-1658998735701)(https://p1-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/501a822a42674798a58032e93e64bc44~tplv-k3u1fbpfcp-watermark.image?)]

示例 2:
输入: head = [1,2,3,4,5], k = 3
输出: [3,2,1,4,5]

  
 
  • 1
  • 2
  • 3

二、解题

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];
    }
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8VTzMtf1-1658998735702)(https://p1-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/f700c3e77d474cf59710419c60c52147~tplv-k3u1fbpfcp-watermark.image?)]

3、时间复杂度

时间复杂度 : O(n)

其中n是链表的长度。

空间复杂度: O(1)

只需要建立常数个变量。

三、总结

有一个特殊情况需要注意,当翻转长度不够k时,定位到end完成后,end==null,说明已经到达链表末尾。

此时需要直接返回。

文章来源: itmonon.blog.csdn.net,作者:恬静的小魔龙,版权归原作者所有,如需转载,请联系作者。

原文链接:itmonon.blog.csdn.net/article/details/126039029

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:cloudbbs@huaweicloud.com进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。