LeetCode Solutions Blog

Rotate List

Difficulty: Medium

Problem Description

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

Key Insights

The rotation can be optimized using the length of the linked list.
If k is greater than the length of the list, only k % length rotations are needed.
The list can be made circular to facilitate easy rotation.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we can follow these steps:

Compute the length of the linked list.
If the list is empty or k is 0, return the head.
Calculate the effective rotations needed as k % length.
Make the linked list circular by connecting the last node to the head.
Find the new tail node which will be at position (length - k) from the start.
Break the circular link to create the rotated list.

Code Solutions

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

def rotateRight(head: ListNode, k: int) -> ListNode:
    if not head or not head.next:
        return head

    # Step 1: Calculate the length of the list
    length = 1
    current = head
    while current.next:
        current = current.next
        length += 1

    # Step 2: Compute effective rotations
    k = k % length
    if k == 0:
        return head

    # Step 3: Make the list circular
    current.next = head

    # Step 4: Find the new tail (length - k - 1)
    new_tail = head
    for _ in range(length - k - 1):
        new_tail = new_tail.next

    # Step 5: Update the head and break the circular link
    new_head = new_tail.next
    new_tail.next = None

    return new_head