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