k个一组翻转链表 #48
Description
习题
出处：LeetCode 算法第25题
给出一个链表，每 k 个节点一组进行翻转，并返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么将最后剩余节点保持原有顺序。
示例 :
给定这个链表：
1->2->3->4->5当 k = 2 时，应当返回:
2->1->4->3->5当 k = 3 时，应当返回:
3->2->1->4->5说明 :
- 你的算法只能使用常数的额外空间。
- 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
思路
先统计有几个k个元素，对每k个元素进行链表的翻转，再组成长链表
解答
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
function ListNode(val) {
this.val = val;
this.next = null;
}
var reverseKItem = function (head, k) {
var start = head;
var tail = head;
var current = 0;
var prev = next = null;
while (head && current < k) {
next = head.next;
head.next = prev;
prev = head;
start = head;
current++;
head = next;
}
tail.next = next;
return [start, tail];
}
var reverseKGroup = function (head, k) {
if (!head || !head.next || k <= 1) {
return head;
}
// 计算链表的长度
var length = 0;
var tempNode = head;
while (tempNode) {
length++;
tempNode = tempNode.next;
}
var empty = new ListNode();
var prev = empty;
var i = 0;
while (head && head.next) {
if (k > (length - i)) break;
var [rHead, rTail] = reverseKItem(head, k);
prev.next = rHead;
prev = rTail;
head = rTail.next;
i += k;
}
return empty.next || head;
};
var head = new ListNode(1);
var aaa = head;
head.next = new ListNode(2);
head = head.next;
head.next = new ListNode(3);
head = head.next;
head.next = new ListNode(4);
head = head.next;
head.next = new ListNode(5);
console.log(reverseKGroup(aaa, 3));