千锋教育-做有情怀、有良心、有品质的职业教育机构

400-811-9990
手机站
千锋教育

千锋学习站 | 随时随地免费学

千锋教育

扫一扫进入千锋手机站

领取全套视频
千锋教育

关注千锋学习站小程序
随时随地免费学习课程

当前位置:北京千锋IT培训  >  技术干货  >  大数据技术干货  > 算法题(力扣)--K个一组翻转链表

算法题(力扣)--K个一组翻转链表

来源:千锋教育
发布人:qyf
时间: 2022-11-08 14:39:05

  题目描述

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

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

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

  示例:

  给你这个链表:1->2->3->4->5

  当 k = 2 时,应当返回: 2->1->4->3->5

  当 k = 3 时,应当返回: 3->2->1->4->5

  说明:

  你的算法只能使用常数的额外空间。

  你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。

  题目解析

  这道算法题可以说是 两两交换链表中的节点 的升级版, 区别就是反转的子链表节点个数变成了自定义.

  总体思路还是一样的, 具体可以分为两个处理模块:

  根据 k 划分若干个需要反转的子链表, 连接反转后的子链表, 最后不足 k 的子链表保持不变

  设置哨兵 dummy 指向 head , 为了能找到反转后的链表头结点;

  循环 k 确定需要 反转子链表 的范围:

  循环完成, 确定子链表可以反转

  假设 A , B 子链表邻接且都可以反转

  指针 start 指向 A 的头结点, end 指向 A 的尾结点, nxt 指向 B 的头结点

  start -> end 反转后, start 变成了 A 的尾结点, start -> next = nxt , 反转后的 A 链表指向了 B

  重置 start 为 B 的头节点, end 为 B 的尾结点, nxt 为下一个子链表头节点, 反转 B 链表

  重复上面动作, 知道 循环终止

  循环终止, 剩余节点不足 k , 终止反转, 返回链表

  反转子链表

  假设子链表前三个节点为 a, b, c ,设置指针 pre, cur, nxt , 初始化 pre 值为 null, cur值为 a , nxt 值为 a , 这三个指针位置不变且相邻

  终止条件: cur 不为空

  将当前节点的指针指向上一个节点

  cur 指向 nxt ( nxt 值为 b )

  cur 指向 pre ( cur 指向 null )

  cur 赋值给 pre ( pre 值为 a ) , nxt 赋值给 cur ( cur 值为 b )

  在执行 步骤 1 ( nxt 值为 c , 到此相当于 pre, cur , nxt 指向依次向后移动 1 位 )

  重复上面动作

  参考代码:

  反转链表

1

  递归解法

2

  迭代解法

3

  复杂度分析

  时间复杂度: O( nk ) , 最好情况 O( n ), 最坏情况 O( n^2 )

  空间复杂度: O( 1 )

声明:本站稿件版权均属千锋教育所有,未经许可不得擅自转载。

10年以上业内强师集结,手把手带你蜕变精英

请您保持通讯畅通,专属学习老师24小时内将与您1V1沟通

免费领取

今日已有369人领取成功

刘同学 138****2860 刚刚成功领取
王同学 131****2015 刚刚成功领取
张同学 133****4652 刚刚成功领取
李同学 135****8607 刚刚成功领取
杨同学 132****5667 刚刚成功领取
岳同学 134****6652 刚刚成功领取
梁同学 157****2950 刚刚成功领取
刘同学 189****1015 刚刚成功领取
张同学 155****4678 刚刚成功领取
邹同学 139****2907 刚刚成功领取
董同学 138****2867 刚刚成功领取
周同学 136****3602 刚刚成功领取

猜你喜欢LIKE

算法题(力扣)--盛水最多的容器

2022-11-08

nio和bio的区别为啥nio好?

2022-11-08

算法题(力扣)两数之和

2022-11-08

最新文章NEW

算法题(力扣)-有效的括号

2022-11-14

DAU(日活)为何会骤降?给出分析思路

2022-11-14

算法题(力扣)--K个一组翻转链表

2022-11-08

相关推荐HOT

快速通道 更多>>

最新开班信息 更多>>

网友热搜 更多>>