Rotate List - LeetCodee

Problem Description

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

Examples

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]

Jump to Solution: Python Java C++ JavaScript C#

Python Solution


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def rotateRight(head: Optional[ListNode], k: int) -> Optional[ListNode]:
    if not head or not head.next or k == 0:
        return head
    
    # Calculate length and get the last node
    curr = head
    length = 1
    while curr.next:
        curr = curr.next
        length += 1
    
    # Make the list circular
    curr.next = head
    
    # Calculate actual rotation needed
    k = k % length
    
    # Find new tail and head
    steps = length - k
    curr = head
    for _ in range(steps - 1):
        curr = curr.next
    
    # Break the circular list
    new_head = curr.next
    curr.next = None
    
    return new_head

Java Solution


class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) {
            return head;
        }
        
        // Calculate length and get the last node
        ListNode curr = head;
        int length = 1;
        while (curr.next != null) {
            curr = curr.next;
            length++;
        }
        
        // Make the list circular
        curr.next = head;
        
        // Calculate actual rotation needed
        k = k % length;
        
        // Find new tail and head
        int steps = length - k;
        curr = head;
        for (int i = 0; i < steps - 1; i++) {
            curr = curr.next;
        }
        
        // Break the circular list
        ListNode newHead = curr.next;
        curr.next = null;
        
        return newHead;
    }
}

C++ Solution


class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head || !head->next || k == 0) {
            return head;
        }
        
        // Calculate length and get the last node
        ListNode* curr = head;
        int length = 1;
        while (curr->next) {
            curr = curr->next;
            length++;
        }
        
        // Make the list circular
        curr->next = head;
        
        // Calculate actual rotation needed
        k = k % length;
        
        // Find new tail and head
        int steps = length - k;
        curr = head;
        for (int i = 0; i < steps - 1; i++) {
            curr = curr->next;
        }
        
        // Break the circular list
        ListNode* newHead = curr->next;
        curr->next = nullptr;
        
        return newHead;
    }
};

JavaScript Solution


/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var rotateRight = function(head, k) {
    if (!head || !head.next || k === 0) {
        return head;
    }
    
    // Calculate length and get the last node
    let curr = head;
    let length = 1;
    while (curr.next) {
        curr = curr.next;
        length++;
    }
    
    // Make the list circular
    curr.next = head;
    
    // Calculate actual rotation needed
    k = k % length;
    
    // Find new tail and head
    let steps = length - k;
    curr = head;
    for (let i = 0; i < steps - 1; i++) {
        curr = curr.next;
    }
    
    // Break the circular list
    const newHead = curr.next;
    curr.next = null;
    
    return newHead;
};

C# Solution


public class Solution {
    public ListNode RotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) {
            return head;
        }
        
        // Calculate length and get the last node
        ListNode curr = head;
        int length = 1;
        while (curr.next != null) {
            curr = curr.next;
            length++;
        }
        
        // Make the list circular
        curr.next = head;
        
        // Calculate actual rotation needed
        k = k % length;
        
        // Find new tail and head
        int steps = length - k;
        curr = head;
        for (int i = 0; i < steps - 1; i++) {
            curr = curr.next;
        }
        
        // Break the circular list
        ListNode newHead = curr.next;
        curr.next = null;
        
        return newHead;
    }
}

Complexity Analysis

Time Complexity: O(n) where n is the length of the linked list
Space Complexity: O(1) as we only use a few pointers

Solution Explanation

This solution uses a three-step approach to rotate the linked list:

Step 1: Calculate length
- Traverse list to find length
- Keep track of last node
Step 2: Make list circular
- Connect last node to head
- Calculate actual rotation needed
Step 3: Break at new position
- Find new tail position
- Break circular connection
- Return new head

Key points:

Handle edge cases first
Use modulo for large k
Efficient single pass
Constant extra space