Rotate List medium

Problem Statement

Given the head of a linked list, rotate the list to the right by k places.

Example 1:

Input: head = [1,2,3,4,5], k = 2 Output: [4,5,1,2,3]

Example 2:

Input: head = [0,1,2], k = 4 Output: [2,0,1]

Steps:

1. Find the list length: Traverse the linked list to determine its length, n.
2. Handle edge cases:
   • If the list is empty (n === 0), return null.
   • If k is greater than or equal to the length of the list, effectively, we rotate it by k % n places. This handles cases where k is much larger than the list's length.
3. Find the new tail and new head: Traverse the list to the node at index n - (k % n) - 1. This will be the new tail. The node after the new tail will be the new head.
4. Connect the new tail to the head: Set the next of the new tail to the original head.
5. Update the head: Set the head of the list to the new head.
6. Return the new head: Return the updated head of the rotated linked list.

Explanation

The key idea is to find the point where the list needs to be broken and reconnected. By calculating n - (k % n) - 1, we find the index of the node that will become the new tail. Then, we simply redirect the next pointer of the new tail to the original head, effectively creating a circular rotation.

Code

class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val===undefined ? 0 : val)
        this.next = (next===undefined ? null : next)
    }
}

function rotateRight(head: ListNode | null, k: number): ListNode | null {
    if (!head) return null;

    let n = 0;
    let tail = head;
    while (tail.next) {
        n++;
        tail = tail.next;
    }
    n++; // Include the last node in the count.

    k = k % n; // Handle k larger than list length

    if (k === 0) return head; // No rotation needed

    let newTail = head;
    for (let i = 0; i < n - k - 1; i++) {
        newTail = newTail.next!;
    }

    const newHead = newTail.next!;
    newTail.next = null; // Set the old tail's next to null
    tail.next = head; // Connect the old tail to the original head
    
    return newHead;
}


//Example Usage
const head1 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
const rotated1 = rotateRight(head1, 2); // Output: [4,5,1,2,3]


const head2 = new ListNode(0, new ListNode(1, new ListNode(2)));
const rotated2 = rotateRight(head2, 4); // Output: [2,0,1]

// Helper function to print the linked list
function printList(head: ListNode | null): void {
    let current = head;
    let output = "";
    while (current) {
        output += current.val + " ";
        current = current.next;
    }
    console.log(output);
}

printList(rotated1); // prints 4 5 1 2 3
printList(rotated2); // prints 2 0 1

Complexity

• Time Complexity: O(N), where N is the number of nodes in the linked list. We traverse the list twice in the worst case.
• Space Complexity: O(1). The algorithm uses constant extra space.