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 length of the linked list: Traverse the list to determine its length.
2. Handle edge cases: If the list is empty or k is 0, return the original list. If k is greater than or equal to the length of the list, effectively k becomes k % length. This handles cases where we rotate more than the list's length.
3. Find the new tail: Traverse the list to the node that will become the new tail. This node is located at length - (k % length) -1 index (0-indexed).
4. Connect the new tail to the head: Make the next pointer of the new tail point to the original head.
5. Find the new head: The node after the new tail becomes the new head.
6. Update the tail: Set the next pointer of the old tail to null.
7. Return the new head:

Explanation:

The key idea is to find the point where the list needs to be broken and rejoined. Instead of rotating the list k times (which would be inefficient for large k), we calculate the position of the new tail, which is length - (k % length) - 1. We then connect the new tail to the head, making the node after the new tail the new head, and finally setting the next pointer of the original tail to null to close the rotated list.

Code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || k == 0) return head;

        ListNode tail = head;
        int length = 1;
        while (tail.next != null) {
            tail = tail.next;
            length++;
        }

        k %= length; // Handle cases where k >= length

        if (k == 0) return head;

        int newTailIndex = length - k -1;

        ListNode newTail = head;
        for (int i = 0; i < newTailIndex; i++) {
            newTail = newTail.next;
        }

        ListNode newHead = newTail.next;
        tail.next = head;
        newTail.next = null;


        return newHead;
    }
}

Complexity:

• Time Complexity: O(N), where N is the length of the linked list. We traverse the list twice in the worst case.
• Space Complexity: O(1). We use only a constant amount of extra space.