Rotate Doubly Linked List by N Nodes

Problem Statement

Given a doubly linked list and a positive integer n, rotate the list counter-clockwise by n nodes. The rotation means moving the first n nodes to the end of the list.

Example

Input: 1 <-> 2 <-> 3 <-> 4 <-> 5, n = 2
Output: 3 <-> 4 <-> 5 <-> 1 <-> 2

Input: 10 <-> 20 <-> 30 <-> 40, n = 1
Output: 20 <-> 30 <-> 40 <-> 10

Brute Force Approach

Intuition

The brute force approach rotates the list one position at a time, n times. Each rotation involves moving the first node to the end of the list.

Algorithm

Repeat n times:
- Remove the head node
- Traverse to the end of the list
- Append the removed node at the end
Update all prev/next pointers appropriately

Code

java

class Node {
    int data;
    Node prev;
    Node next;
    
    Node(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

public class RotateDLL {
    public static Node rotateBruteForce(Node head, int n) {
        if (head == null || head.next == null || n == 0) {
            return head;
        }
        
        // Count nodes to handle n >= length
        int length = 0;
        Node temp = head;
        while (temp != null) {
            length++;
            temp = temp.next;
        }
        
        n = n % length;
        if (n == 0) return head;
        
        // Rotate one by one
        for (int i = 0; i < n; i++) {
            // Save the head
            Node first = head;
            
            // Move head to next
            head = head.next;
            head.prev = null;
            
            // Find the tail
            Node tail = head;
            while (tail.next != null) {
                tail = tail.next;
            }
            
            // Append first node at the end
            tail.next = first;
            first.prev = tail;
            first.next = null;
        }
        
        return head;
    }
    
    public static void printList(Node head) {
        while (head != null) {
            System.out.print(head.data);
            if (head.next != null) System.out.print(" <-> ");
            head = head.next;
        }
        System.out.println();
    }
}

Complexity Analysis

Time Complexity: O(n * k) where k is the rotation count - We traverse to find tail for each rotation
Space Complexity: O(1) - Only using constant extra space

Optimal Approach

Intuition

Instead of rotating one node at a time, we can directly find the new head position and rearrange pointers in a single pass. The key insight is that rotating by n means the (n+1)th node becomes the new head, and the first n nodes move to the end.

Algorithm

Find the length of the list and the tail node in one traversal
Calculate effective rotation (n % length)
Find the new head (at position n+1) and the new tail (at position n)
Rearrange pointers:
- Connect old tail to old head
- Set new head's prev to null
- Set new tail's next to null

Code

java

class Node {
    int data;
    Node prev;
    Node next;
    
    Node(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

public class RotateDLLOptimal {
    public static Node rotateOptimal(Node head, int n) {
        if (head == null || head.next == null || n == 0) {
            return head;
        }
        
        // Find length and tail in one traversal
        int length = 1;
        Node tail = head;
        while (tail.next != null) {
            length++;
            tail = tail.next;
        }
        
        // Handle n >= length
        n = n % length;
        if (n == 0) return head;
        
        // Find the new tail (node at position n)
        Node newTail = head;
        for (int i = 1; i < n; i++) {
            newTail = newTail.next;
        }
        
        // New head is the node after new tail
        Node newHead = newTail.next;
        
        // Rearrange pointers
        // Connect old tail to old head
        tail.next = head;
        head.prev = tail;
        
        // Set new head's prev to null
        newHead.prev = null;
        
        // Set new tail's next to null
        newTail.next = null;
        
        return newHead;
    }
    
    public static void printList(Node head) {
        while (head != null) {
            System.out.print(head.data);
            if (head.next != null) System.out.print(" <-> ");
            head = head.next;
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        // Create sample list: 1 <-> 2 <-> 3 <-> 4 <-> 5
        Node head = new Node(1);
        Node curr = head;
        for (int i = 2; i <= 5; i++) {
            Node newNode = new Node(i);
            curr.next = newNode;
            newNode.prev = curr;
            curr = newNode;
        }
        
        int n = 2;
        System.out.print("Original list: ");
        printList(head);
        
        head = rotateOptimal(head, n);
        
        System.out.print("After rotating by " + n + " nodes: ");
        printList(head);
    }
}

Complexity Analysis

Time Complexity: O(n) - Single traversal to find length and new positions
Space Complexity: O(1) - Only using constant extra space

Key Takeaways

Modulo Operation: Always handle n >= length by using n % length
Single Traversal: Find both length and tail in one pass for efficiency
Pointer Rearrangement: The key is identifying the four pointers to update:
- Old tail → Old head connection
- New head's prev becomes null
- New tail's next becomes null
DLL Advantage: The prev pointer makes it easy to set up the new connections
Edge Cases: Handle empty list, single node, and n = 0 cases
Visualization: Think of the list as a circular structure temporarily, then "break" it at the new position

Rotate Doubly Linked list by N nodes

Rotate Doubly Linked List by N Nodes

Problem Statement

Example

Brute Force Approach

Intuition

Algorithm

Code

Complexity Analysis

Optimal Approach

Intuition

Algorithm

Code

Complexity Analysis

Key Takeaways