K个一组翻转链表
- 更新:2020-05-16 21:10:05
- 首发:2020-05-16 21:04:29
- 源代码
- 2566
LeetCode 25. K 个一组翻转链表 https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
LintCode 450. K组翻转链表 https://www.lintcode.com/problem/reverse-nodes-in-k-group/
这是一道用常规思路就能解的算法题。目标清晰、题目易懂,不涉及复杂的算法。
按照题目要求,遍历链表,遍历的同时每经过k
个节点就进行一次翻转。需要注意的是,第一次翻转后,记录下整个链表的head
作为返回值。从第二次翻转开始,需要将之前翻转过的最后一个结点与新翻转后的第一个结点相连。
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
export const reverseKGroup = function (head, k) {
let sum = 0 // 记录进行的结点个数
let start = head // 记录每次翻转的第一个元素
let res = head // 返回值:如果进行过翻转,则为第一次翻转的最后一个结点
const queue = [] // 使用队列,方便连接上一次翻转的链表,最大长度为2
while (head) { // 遍历一次链表
if (++sum === k) { // 如果经过了k个结点,则翻转从start到head的一段结点
const headNext = head.next
queue.push(start) // 计入队列
let next = head.next
for (let i = 0; i < sum - 1; i++) { // 翻转结点
const tmp = start.next
start.next = next
next = start
start = tmp
}
start.next = next // 最后一个结点
if (queue.length === 1) { // 判断是否为第一次翻转
res = start
} else {
const la = queue.shift() // 连接上一次翻转的链表
la.next = head
}
sum = 0 // 重置计数
start = headNext
head = headNext
} else {
head = head.next
}
}
return res
}
以往的算法题,暴力解法通常都无法通过测试,这题不需要什么操作技巧,就按题目要求的作解即可,编写过程中需要考虑清楚数据是如何变化的,做好边界条件的处理即可。
这道题还可以使用栈
来解答。不妨再进一步思考,从后往前以k
个为一组进行翻转如何实现?
这道题和合并K个排序链表算是链表
中的少见的难题,其实这两道题整体思路都不复杂。
这是我的算法练习解题记录https://github.com/yi-ge/js-practice。欢迎加我微信探讨算法!
除特别注明外,本站所有文章均为原创。原创文章均已备案且受著作权保护,未经作者书面授权,请勿转载。
打赏
交流区
暂无内容




由于我使用的方案并不需要“快捷指令”等APP的配合。也无需任何系统权限。因此存在被滥用可能,请大家不要因为此事联系我,谢谢。
直接问AI吧😂
作者老哥,代码不开源。可以大致说一下实现思路吗😕
谢谢,你写的最详细,也很有效的解决了撕裂问题
很棒的教程,比我之前配置ap的方式更优雅