本文主要是介绍leetcode算法题之 K 个一组翻转链表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
照我说这道题其实是披着困难皮的中等题目,问题如下:
题目地址
给你链表的头节点 head
,每 k
个节点一组进行翻转,请你返回修改后的链表。
k
是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k
的整数倍,那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。
解法:
首先我们来看一个更简单的问题,就是如何进行原地反转链表
反转链表
其实很简单,通过几个变量就可以实现
pre变量保存上一个节点,初始值为null,cur变量保存当前节点,初始值为我们传进去的节点,每次遍历时用next变量保存下一个节点,然后把当前节点的next值指向上一个节点即可,直到cur变量为null,我们返回pre,即是最后一个节点
var reverse = (head) => {let pre = null, cur = headwhile (cur !== null) {const next = cur.nextcur.next = prepre = curcur = next}return pre
}
那如果我们想把一串链表里的子链表反转应该怎么搞呢?也简单,加入结束节点判断即可
end为结束节点,当遍历到时,停止遍历返回即可,如果刚好是链表最后一个,那end为null,就和我们上面的代码一致
var reverse = (head, end) => {let pre = null, cur = headwhile (cur !== end) {const next = cur.nextcur.next = prepre = curcur = next}return pre
}
有了这个方法接下来的事情就简单了,我们只需要遍历链表,当节点到k时,传进去反转即可
完整代码如下:
/*** @param {ListNode} head* @param {number} k* @return {ListNode}*/
var reverse = (head, end) => {let pre = null, cur = headwhile (cur !== end) {const next = cur.nextcur.next = prepre = curcur = next}return pre
}
var reverseKGroup = function (head, k) {const pre = new ListNode(0, head)let cur = prewhile (true) {let count = k, last = cur, newTail = cur.nextwhile (count > 0) {cur = cur.nextif (!cur) {return pre.next}--count}const next = cur.nextlast.next = reverse(newTail, cur.next)newTail.next = nextcur = newTail}
};
这篇关于leetcode算法题之 K 个一组翻转链表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!