题目描述
将给出的链表中的节点每\ k k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是\ k k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。
要求空间复杂度 \ O(1) O(1)
如果链表中的节点数不是\ k k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。
要求空间复杂度 \ O(1) O(1)
例如：
给定的链表是 1→2→3→4→5
对于 k = 2 , 你应该返回 2→1→4→3→5
对于 k = 3, 你应该返回 3→2→1→4→5
代码：
/*
* function ListNode(x){
* this.val = x;
* this.next = null;
* }
*/
/**
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
//js翻转链表算法
function myReverse(head, tail){
let pre = null;
let cur = head;
// const nex = cur.next;
let nex = null;
while(pre != tail){
nex = cur.next;
cur.next = pre;
pre = cur;
cur = nex;
}
return [tail, head];
}
function reverseKGroup( head , k ) {
const hair = new ListNode(0);
hair.next = head;
let pre = hair;
while(head){
let tail = pre;
//查看剩余部分长度的hi否大于等于K
for(let i =0; i < k; i++){
tail = tail.next;
if(!tail){
return hair.next;
}
}
const cur = tail.next;
[head, tail] = myReverse(head, tail);
pre.next = head;
tail.next = cur;
pre = tail;
head = tail.next;
}
return hair.next;
// write code here
}
module.exports = {
reverseKGroup : reverseKGroup
};
C语言版本的代码：
/*
* function ListNode(x){
* this.val = x;
* this.next = null;
* }
*/
/**
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
function reverseKGroup( head , k ) {
// write code here
var dummy = new ListNode(-1);
dummy.next = head;
var pre=dummy,start=head,end=head,low=head;
while(!low){
for(let i=1;i<k && end!==null;i++ ){
end = end.next
}
if(end === null){
break;
}
//low指针已经走了k步
low = end.next;
end.next = null;
end = start;
start = reverse(start);
//翻转链表之后调整首尾
end.next = low;
pre.next = start;
//重新指定pre start end
pre = end;
start = low;
end = start;
}
return dummy.next;
}
//翻转链表
function reverse(head){
var pre = null,low = null
var cur = head;
while(!cur){
low = cur.next;
cur.next = pre;
pre = cur;
cur = low;
}
//返回翻转后的链表头结点
return pre;
}
module.exports = {
reverseKGroup : reverseKGroup
};