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 linked 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 larger than the length of the list, effectively we only need to rotate by k % length places.
3. Find the (length - (k % length))th node: This node will become the new tail of the rotated list.
4. Break the list: Point the next pointer of the (length - (k % length))th node to None. This separates the list into two parts.
5. Connect the lists: Make the original tail node point to the head node. This completes the rotation.
6. Return the new head: The new head of the rotated list is the node after the (length - (k % length))th node.

Explanation

The key idea is to first find the length of the linked list. Then, we effectively rotate the list by k % length places, which handles cases where k is larger than the list's length. We find the node that should become the new tail, break the list at that point, and then connect the two parts to form the rotated list. This avoids unnecessary traversals and ensures efficient rotation.

Code

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

def rotateRight(head, k):
    if not head or not head.next or k == 0:
        return head

    # Find the length of the linked list
    length = 1
    tail = head
    while tail.next:
        tail = tail.next
        length += 1

    k %= length  # Handle k > length

    if k == 0:
        return head

    # Find the (length - k)th node
    new_tail = head
    for _ in range(length - k -1):
        new_tail = new_tail.next

    new_head = new_tail.next
    tail.next = head
    new_tail.next = None

    return new_head

#Example Usage
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)

k = 2
rotated_head = rotateRight(head, k)

result = []
while rotated_head:
    result.append(rotated_head.val)
    rotated_head = rotated_head.next
print(result) # Output: [4, 5, 1, 2, 3]


head2 = ListNode(0)
head2.next = ListNode(1)
head2.next.next = ListNode(2)
k2 = 4
rotated_head2 = rotateRight(head2,k2)
result2 = []
while rotated_head2:
    result2.append(rotated_head2.val)
    rotated_head2 = rotated_head2.next
print(result2) #Output: [2, 0, 1]

Complexity

• Time Complexity: O(N), where N is the length of the linked list. We traverse the list once to find the length and again to find the new tail.
• Space Complexity: O(1). We use only a constant amount of extra space.