61. Rotate linked lists
Topic describes
Given the head of a linked list, rotate the list to move each node k positions to the right.
The sample
Given a linked list: 1 -> 2 -> 3 -> 4 -> 5
k = 2
5 -> 1 -> 2 -> 3 -> 4 // Move 1 time
4 -> 5 -> 1 -> 2 -> 3 // Move 2 times
Copy the code
k = 6
5 -> 1 -> 2 -> 3 -> 4 // Move 1 time
4 -> 5 -> 1 -> 2 -> 3 // Move 2 times
3 -> 4 -> 5 -> 1 -> 2 // Move 3 times
2 -> 3 -> 4 -> 5 -> 1 // Move 4 times
1 -> 2 -> 3 -> 4 -> 5 // Move 5 times
5 -> 1 -> 2 -> 3 -> 4 // Move 6 times
Copy the code
Their thinking
- Rotating list
- All we need to do is connect the end to the end of the original list and turn it into a circular list to achieve the purpose of rotation
- Point next from the tail to the head
- A closer look at the example above shows that the list is in its original state when the number of moves is a multiple of its length. So the actual number of moves is k % of the list length
- Once the move is complete, we simply break the end of the latest circular list head and return to the new head
- But how do we determine the new header?
Take k = 6. For single linked lists, it is recommended to change finding new headers to finding new endpoints because:
In the first step, we can record the original endpoint, and then use some method to find the current endpoint
1 -> 2 -> 3 -> 4 -> 5The original endpoint is zero5
5 -> 1 -> 2 -> 3 -> 4 // Actually move the original endpoint 1 times next find the current endpoint 4 times
4 -> 5 -> 1 -> 2 -> 3 // Actually move the original tail 2 times next find the current tail 3 times
3 -> 4 -> 5 -> 1 -> 2 // Actually move the original tail 3 times next find the current tail 2 times
2 -> 3 -> 4 -> 5 -> 1 // Actually move the original endpoint 4 times next to find the current endpoint
1 -> 2 -> 3 -> 4 -> 5 // Actually move the original tail 0 times next find the current tail 5 times
5 -> 1 -> 2 -> 3 -> 4 // Actually move the original endpoint 1 times next find the current endpoint 4 times
Copy the code
We can see from the records above
Original tail next = list length – actual number of moves
So: new tail = original tail. Next * number of times
If the new end node is found, the new head node is not at hand.
code
var rotateRight = function (head, k) {
// The list does not exist, has only one element, does not move position
if(! head || ! head.next || ! k)return head;
// Calculate the length of the list and find the end point
let len = 1,
cur = head;
while (cur.next) {
cur = cur.next;
len++;
}
// Point the tail to the head to form a circular linked list
cur.next = head;
// Count the actual number of moves
k = k % len;
// Count the number of times the original tail needs to move
let move = len - k;
while (move) {
cur = cur.next;
move--;
}
// Get the new header
let newHead = cur.next;
// Disassociate the tail from the head
cur.next = null;
// Return a new header
return newHead;
};
Copy the code