轮换链表

说明

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:

1
2
3
4
5
6
Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL

Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

1
2
3
4
5
6
7
8
Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL

Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

实现

  1. 递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
const rotateRight = function(head, k) {
if(!head || k === 0){
return head;
}
let length = 0;
let node = head;
while(node){
length++;
node = node.next;
}
k = k % length;

return rotatet(head, k);
};

function rotatet(node, k){
if(k === 0 ){
return node;
}
let currentNode = node;
let prev = null;
while(currentNode.next){
prev = currentNode;
currentNode = currentNode.next;
}
if(prev){
prev.next = null;
currentNode.next = node;
}
return rotatet(currentNode, k-1);
}

  1. 迭代
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
const rotateRight = function(head, k) {
if( !head || k < 1){
return head;
}

let length = 1;
let current = head;
while(current.next){
length++;
current = current.next;
}

k = k % length;
if(!k){
return head;
}

current.next = head;

let rotateNum = length - k - 1;
while(rotateNum > 0){
head = head.next;
rotateNum--;
}
const newHead = head.next;
head.next = null;
return newHead;
};