前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【力扣刷题】25. K 个一组翻转链表

【力扣刷题】25. K 个一组翻转链表

作者头像
jayjay
发布2022-11-02 16:53:16
2520
发布2022-11-02 16:53:16
举报
文章被收录于专栏:jay_blogjay_blog

一、题目描述

来源:力扣(LeetCode)

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

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

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

进阶:

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

image.png
image.png

示例 2:

image.png
image.png

示例 3:

  示例 4:

提示:

  • 列表中节点的数量在范围 sz 内
  • 1 <= sz <= 5000
  • 0 <= Node.val <= 1000
  • 1 <= k <= sz

二、思路分析

  1. 统计链表的长度
  2. 计算链表翻转的次数 reverse_times=len/k;
  • 如果翻转次数为0,直接返回原链表即可。
  1. 定义多个变量
  • cur_time保存当前翻转的次数(可以用来确定翻转次数)
  • nhead虚拟头结点(一般链表题中都可定义一个不包含数据的哨兵头结点)
  • knext保存下一次翻转的链表头结点(防止后面的链表数据丢失)
  • cur_head当前需要翻转的部分链表的头结点,实际上是头部结点的前一个结点(便于做局部翻转)。
  • cur_tail当前翻转的部分链表的尾部结点,用于在翻转完成后,与knext进行连接,保证数据不会被丢失。
  1. 执行链表的翻转
    1. 将knext指向下一次翻转时候的链表头结点
    1. 使用头插法进行反转(注意要用cur_tail保存局部链表的第一个结点,翻转完成后,它将处于局部链表的最后一个位置,然后将它与后面的链表连接起来)
    1. 将尾部结点重新赋值给头部结点,并且让尾部结点的next指针指向knext
    1. 翻转次数+1
    1. 返回nhead.next;

三、代码实现

四、运行结果

image.png
image.png

总结

参考了别人的解题,这道题在于确定要反转多少次,然后分组进行头插,剩下的接上就行了

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022-03-30,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、题目描述
  • 二、思路分析
  • 三、代码实现
  • 四、运行结果
  • 总结
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档