leetcode算法题之 K 个一组翻转链表

本文主要是介绍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 个一组翻转链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---