Algorithm Gymnastics 17

Rotate a Linked List

Description

An algorithmic exercise that rotates the linked list by n, given the head node of a single linked list and the integer n.

Below are two examples. The linked list passed as an argument and the output after the integer n = 2 rotations.

Note that the value of n can be larger than the length of the linked list.

When n = -2,

Solution Runtime Complexity O(n) n is the length of the linked list. Memory Complexity O(1) No need to use new data structures. Pointer only.

1. First, find the length of the linked list.
2. If n is negative, or if n is greater than the length of the linked list, adjust to the required number of revolutions at the end of the linked list. The adjusted number is always the integer N (0 <= N <n). If the adjusted speed is 0, it just returns the head pointer. This means that no rotation was needed.
3. Find the nth'x'node from the last node in the linked list. It basically reaches node x with a length of "n-N". The next pointer to the node before this node will be the last node in the list and should be updated to point to NULL.
4. From x, go to the last node in the linked list. Causes the head node to update the next pointer after the last node.
5. Create new_head as a new head node. new_head will be at the top of the linked list after performing n rotations.

Since "a picture is worth a thousand words", let's rotate the above linked list with n = 2 using the above algorithm.

Implementation

RotateList.java

class RotateList{

  private int getListSize(LinkedListNode head) {
    LinkedListNode curr = head;
    int listSize = 0;

    while (curr != null) {
       listSize++;
       curr = curr.next;
     }
     return listSize;
  }

  private int adjustRotatationsNeeded(int n, int length) {
    return n < 0 ? length - (n * -1) % length : n % length;
  }

   public LinkedListNode rotate_list(LinkedListNode head, int n) {
     
     int listSize = 0;
     listSize = getListSize(head);

     n = adjustRotatationsNeeded(n, listSize);

     if (n == 0) {
       return head;
     }

    // Find the startNode of rotated list.
    // If we have 1,2,3,4,5 where n = 2,
    // 4 is the start of rotated list

     LinkedListNode temp = head;
     int rotationsCount = listSize - n - 1;
     while(rotationsCount > 0) {
       temp = temp.next;
       rotationsCount--;
     }

     LinkedListNode new_head = temp.next;
     temp.next = null;

     LinkedListNode tail = new_head;
     while (tail.next != null) {
       tail = tail.next;
     }

     tail.next = head;
     head = new_head;
     
    return new_head;
  }
}