原题地址：K 个一组翻转链表
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
示例 :
给定这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5
说明 :
- 你的算法只能使用常数的额外空间。
- 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
准备工作
定义链表节点：
function ListNode(val) {
this.val = val;
this.next = null;
}
数组转链表，方便测试数据的输入：
function arrayT[两两交换链表中的节点](https://blog.lihaiping.cn/archives/swap-nodes-in-pairs)oList(array) {
let node = null;
for (let i = array.length - 1; i >= 0; i --) {
let newNode = new ListNode(array[i]);
newNode.next = node;
node = newNode;
}
return node;
}
链表转字符串，方便测试结果的显示：
function listToString(node) {
return node ? `${node.val}${node.next ? ` -> ${listToString(node.next)}` : '' }` : null;
}
遍历
与上一题 两两交换链表中的节点 一样，我们也可以遍历链表，然后k个节点一组进行翻转。确定分组的尾节点可以通过设置快慢两个指针来达到，快指针先走k步，到达一组的末尾。
具体实现如下：
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
const reverseKGroup1 = function(head, k) {
if (k < 2) {
return head;
}
let prevHead = new ListNode(null);
prevHead.next = head;
let [slow, fast] = [prevHead, prevHead]; // 快慢指针
let [p, q, pr] = [null, null, null]; // 分别指向要翻转的节点、翻转后的next、翻转前的next
// 快指针移动，完毕后快指针指向分组的最后一个节点，慢指针则指向分组第一个节点的前一个节点
for (let i = 0; i < k; i ++) {
fast = fast && fast.next;
}
while (fast) {
p = slow.next; // p指向第一个节点
q = fast.next; // 第一个节点翻转后指向下一个分组
pr = p.next; // pr是p的next
slow.next = fast; // 上一组的next指向这一组的最后一个节点
[slow, fast] = [p, p];
for (let i = 0; i < k - 1; i ++) {
// 翻转一个节点
p.next = q;
q = p;
p = pr;
pr = p && p.next;
}
p.next = q;
for (let i = 0; i < k && fast; i ++) {
fast = fast.next;
}
}
return prevHead.next;
};
测试：
let start = new Date();
const test = reverseKGroup1;
console.log(listToString(test(arrayToList([1, 2, 3, 4, 5, 6, 7, 8]), 2))); // 2 -> 1 -> 4 -> 3 -> 6 -> 5 -> 8 -> 7
console.log(listToString(test(arrayToList([1, 2, 3, 4, 5]), 3))); // 3 -> 2 -> 1 -> 4 -> 5
console.log(new Date().getTime() - start.getTime()); // 3
时间复杂度： 遍历了两次，时间复杂度为O(2n)=O(n)
空间复杂度： 常数级额外空间，空间复杂度为O(1)
栈
我们要将链表进行翻转，这刚好与栈先进后出的特点相匹配，所以我们可以利用栈来完成翻转的过程。 具体实现如下：
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
const reverseKGroup2 = function(head, k) {
if (k < 2) {
return head;
}
let stack = []; // 定义栈
let preHead = new ListNode(null);
preHead.next = head;
let [slow, fast] = [preHead, preHead];
while (1) {
// 遍历一组节点并依次入栈
for (let i = 0; i < k && fast.next; i ++) {
stack.push(fast.next);
fast = fast.next;
}
// 如果栈长度不为k，证明已不足一组，直接退出循环即可
if (stack.length < k) {
break;
}
// 利用栈完成翻转
stack[0].next = fast.next;
while (stack.length > 0) {
slow.next = stack.pop();
slow = slow.next;
}
fast = slow;
}
return preHead.next;
};
测试：
let start = new Date();
const test = reverseKGroup2;
console.log(listToString(test(arrayToList([1, 2, 3, 4, 5, 6, 7, 8]), 2))); // 2 -> 1 -> 4 -> 3 -> 6 -> 5 -> 8 -> 7
console.log(listToString(test(arrayToList([1, 2, 3, 4, 5]), 3))); // 3 -> 2 -> 1 -> 4 -> 5
console.log(new Date().getTime() - start.getTime()); // 3
时间复杂度： 时间复杂度为O(n)
空间复杂度： 入栈的元素最多为k个，空间复杂度为O(k)
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 17,2019