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 excessive rotations: Since we're rotating right, k can be larger than n. We only need to consider the effective rotation, which is k % n. This handles cases where k is greater than or equal to n.
3. Find the new tail: Traverse the list n - (k % n) nodes from the head. This node will become the new tail.
4. Find the new head: The node after the new tail is the new head.
5. Connect the list: Make the next pointer of the new tail point to the original head. Make the next pointer of the node before the new head null (the old tail).

Explanation

The core idea is to find the split point in the linked list where we cut the list to rotate it. By calculating the effective rotation (k % n), we find how many nodes need to be moved to the beginning. We traverse the list to locate the new tail and then reconnect the list.

Code

using System;

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    public ListNode RotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) return head;

        int n = 1; // Length of the list
        ListNode tail = head;
        while (tail.next != null) {
            n++;
            tail = tail.next;
        }

        k %= n; // Handle excessive rotations

        if (k == 0) return head;


        int newTailIndex = n - k;
        ListNode newTail = head;
        for (int i = 1; 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 number of nodes in the linked list. We traverse the list at most twice.
• Space Complexity: O(1). We use constant extra space. The solution is in-place.