Leetcode 61 - Rotate list

Note:

  • Use stack to store vals and rotate them is really naive.
  • Use double pointers to find the new head;
  • img

Question:

Given the head of a linked list, rotate the list to the right by k places.

Example:

img

1
2
Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]

Code:

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
32
33
34
35
36
37
38
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var rotateRight = function(head, k) {
if (!head || k === 0) return head;
let tmp = head;
let length = 0;
while (tmp) {
length++;
tmp = tmp.next;
}
k %= length;
if (k === 0) return head;

let slow = head;
let fast = head;
while (k > 0) {
fast = fast.next;
k--;
}
while (fast.next) {
slow = slow.next;
fast = fast.next;
}
let res = slow.next;
slow.next = null;
fast.next = head;
return res;
};