Linked List Part 5: Rotation

Rotating a linked list involves shifting its elements to the right by a specified number of places. This can be particularly useful in various applications, such as implementing circular buffers or rotating elements in a queue. We will break down the code that accomplishes this rotation, explaining each method and its role in the process.

Overview

The primary function of our code is to rotate the linked list to the right by k places. This involves three main steps:

1. Calculate the size of the list and handle edge cases.
2. Determine the new head of the list after rotation.
3. Update the tail of the list.

Here’s a detailed explanation of the methods involved:

Method: rotate(int k)

public void rotate (int k){
        this.head = this.rotate(this.head, k);
        //udpate tail value
       this.tail = this.travelToTail();
}

• Purpose: Public method to rotate the linked list by k places.
• Implementation:
  • Calls the rotate method (which handles the actual rotation logic) and updates the head of the list.
  • Updates the tail of the list by calling travelToTail, which finds the new tail after the rotation. 

Method: travelToTail() #

private Node travelToTail () {
        Node slow = head; //it will store the mid node
        Node fast = head; //it will store the last node
 
        while (fast.next != null && fast.next.next != null){ 
            slow = slow.next; 
            fast = fast.next.next; 
        } 
 
        if(fast.next != null){
             while(fast.next != null){
                 fast = fast.next;
             }
        }
        return fast;
    }

• Purpose: Helper method to find the last node (tail) of the list.
• Implementation:
  • Uses two pointers, slow and fast, to traverse the list. slow moves one step at a time, while fast moves two steps at a time.
  • When fast reaches the end, slow will be at the middle node (useful for other operations like finding the middle node).
  • If fast.next is not null, fast will be moved to the end of the list.
  • Returns the fast node, which is the tail of the list.

Method: rotate(Node head, int k)

/* Rotate the list to the right by k places. */
    protected static Node rotate (Node head, int k){
        
        if(k == 0 || head == null){
            return head;
        }
        int size = 1;
        Node current = head;
        
        //travel in the list until the last node
        while(current.next != null){
            size++;
            current = current.next;
        }
        current.next = head;
        k = k % size; //ensure that k is below the size of the linked list
        
        //travel until the node that need to be split
        for(int i = 0; i < size - k; i++){
            current = current.next;
        }
        head = current.next;
        current.next = null;
        return head;
    }

• Purpose: Rotates the linked list to the right by k places.
• Implementation:
  • Edge Cases: If k is 0 or the list is empty, the list remains unchanged.
  • Calculate Size: Traverse the list to determine its size.
  • Form Circular List: Connect the end of the list to the head to simplify rotation.
  • Find New Head: Use the value of k modulo the size to handle cases where k is larger than the list size. Traverse to find the node that will become the new tail.
  • Break Circular Link: Update the head to the new start and set the old tail’s next reference to null to finalize the rotation.

Time and Space Complexity

• Time Complexity: O(n), where n is the number of nodes in the linked list. The list is traversed a few times, but each traversal is linear in time.
• Space Complexity: O(1). The rotation is done in-place without requiring additional space proportional to the size of the list.

Conclusion

Rotating a linked list is a powerful technique for manipulating list data in various applications. By leveraging a circular list approach and careful pointer management, we can efficiently rotate the list with minimal overhead. This approach ensures that we maintain linear time complexity and constant space complexity, making it suitable for large lists and real-time applications.