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. Screen Shot 2020-01-22 at 5.20.32.png

When n = -2, Screen Shot 2020-01-22 at 5.20.53.png

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. Screen Shot 2020-01-22 at 5.37.14.png Screen Shot 2020-01-22 at 5.37.29.png Screen Shot 2020-01-22 at 5.37.44.png Screen Shot 2020-01-22 at 5.37.57.png Screen Shot 2020-01-22 at 5.38.11.png Screen Shot 2020-01-22 at 5.38.23.png

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;
  }
}

Recommended Posts

Algorithm gymnastics 12
Algorithm gymnastics 3
Algorithm gymnastics 9
Algorithm gymnastics 14
Algorithm gymnastics 2
Algorithm gymnastics 7
Algorithm Gymnastics 15
Algorithm Gymnastics 16
Algorithm Gymnastics 17
Algorithm Gymnastics 18
Algorithm gymnastics 11
Algorithm gymnastics 5
Algorithm gymnastics 4
Algorithm Gymnastics 24 Subsets
Algorithm Gymnastics 23 Merge Intervals
Algorithm Gymnastics 20 Remove Duplicates
Algorithm Gymnastics 21 LinkedList Cycle
Algorithm Gymnastics 24 Cyclic Sort
Algorithm Gymnastics 19 No-repeat Substring
Algorithm exercise 6
Algorithm Gymnastics 24 Reverse a Linked List
Python algorithm
Algorithm exercises 13
Algorithm Gymnastics 20 Pair with Target Sum
Algorithm Gymnastics 22 Squaring a Sorted Array
Python memorandum (algorithm)
Dictionary learning algorithm
String search algorithm