algoadvance

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

Example

Given the list: 1->2->3->4->5, and k = 2, the list becomes 4->5->1->2->3.

Clarifying Questions

  1. What should be returned if k is zero?
    • The list should remain unchanged.
  2. What should be returned if the list is empty or contains only a single node?
    • The list should remain unchanged in these cases.
  3. What if k is greater than the length of the list?
    • If k is greater than the length of the list, then k should effectively be k % n where n is the length of the list.
  4. Is the definition of rotate meaning that we move the last k elements to the front?
    • Yes, the last k elements should be moved to the front.

Strategy

To rotate the list:

  1. Calculate List Length:
    • Traverse through the list to determine its length.
  2. Normalize k:
    • Adjust k such that 0 <= k < length (i.e., k = k % length).
  3. Finding the New Head:
    • If k = 0 after normalization, no rotation is needed.
    • Otherwise, find the new head of the rotated list. This involves identifying the node that will become the last node after rotation.
  4. Rearrange Pointers:
    • Reconnect the nodes such that the list is rotated appropriately.

Code

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 or k == 0:
        return head

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

    # Connect the tail to the head to make it circular
    current.next = head

    # Compute the effective rotations needed
    k = k % length
    steps_to_new_head = length - k

    # Find the new head and the new tail
    new_tail = head
    for _ in range(steps_to_new_head - 1):
        new_tail = new_tail.next
    
    new_head = new_tail.next
    new_tail.next = None

    return new_head

Time Complexity

Thus, the time complexity is O(n).

Explanation

  1. Length Calculation:
    • First, traverse the list to count the number of nodes.
  2. Forming a Circular List:
    • Connect the last node to the head to form a circular linked list.
  3. Effective Rotations:
    • Compute k % length to handle cases where k is larger than the list length.
  4. New Head and Tail:
    • Iterate to find the new tail towards the end of the list, which will break the circular link to form the newly rotated list.

Try our interview co-pilot at AlgoAdvance.com