61.rotate-list.md

61. Rotate List

Hints

• Can you find the new head and tail after rotation?
• What's the effective number of rotations when k is larger than the list size?
• How can you use the concept of finding the k-th node from the end?

Breakdowns

1. How do you handle k larger than the list size?

• Calculate the effective rotation steps as k % size
• This ensures we don't do unnecessary full rotations

2. How do you find the new head and tail?

• The new tail is at position size - k from the start
• The new head is the node after the new tail
• Use the two pointers technique to find the k-th node from the end

3. How do you reconnect the list?

• Break the link at the new tail
• Connect the original tail to the original head
• Return the new head

Key Insights

1. To rotate the list by k steps, we can think of it as removing the last k nodes and moving them to the front.
2. The effective rotation steps is k % size to handle cases where k is larger than the list size.
3. We can use the two-pointer technique (similar to 19. Remove Nth Node From End of List) to find the new tail efficiently.
4. The problem reduces to finding the new head and tail, then reconnecting the list appropriately.

Think of the linked list as a circle temporarily, then break at the right place.

Iterative

To rotate the list, we need to find the new head and tail after the rotation.

1 -> 2 -> 3 -> 4 -> 5
          ^    ^
          tail |
              new head

1. Calculate the size of the list.
2. Calculate the effective rotation steps as k % size.
3. Find the new tail which is at position size - k. (The k node from the end of the list)
4. Break the link at the new tail and connect it to the head.

k = 2
1 -> 2 -> 3 -> 4 -> 5
*              *       // the 2nd node from the end
head      |    |    |
      previous |    |
               |    |
             slow   last

previous?.next = null   // 3 -> null
newHead = slow          // 4
last.next = head    // 5 -> 1

// Result
4 -> 5 -> 1 -> 2 -> 3

fun rotateRight(head: ListNode?, k: Int): ListNode? {
    if (head == null || head.next == null) return head

    var size = 0
    var current = head
    var last = head
    while (current != null) {
        size++
        last = current
        current = current.next
    }
    val kk = k % size
    if (kk == 0) return head

    // Use the same technique as [19. Remove Nth Node From End of List](../leetcode/19.remove-nth-node-from-end-of-list.md)
    var previous: ListNode? = null
    var slow = head
    var fast = head
    var i = 0
    while (i < kk) {
        fast = fast?.next
        i++
    }
    while (fast != null) {
        previous = slow
        slow = slow?.next
        fast = fast?.next
    }
    // Break the link at the new tail
    previous?.next = null

    // Update the new head and reconnect the list
    val newHead = slow
    last?.next = head
    return newHead
}

• Time Complexity: O(N), where N is the number of nodes in the list.
• Space Complexity: O(1), we only use a few pointers.

Edge Cases

• k = 0: Return the head as is
• k = size: Return the head as is (full rotation)
• k > size: Use k % size to get effective rotation steps
• Single node: Return the head as is

Pitfalls

• Not handling k > size: Always calculate k % size to get the effective rotation steps
• Not preserving the last node: Need to keep track of the last node to connect it to the original head
• Not handling empty or single node lists: These cases should be handled separately
• Not breaking the link at the new tail: This can lead to circular lists

Similar or Follow-up Problems

• 19. Remove Nth Node From End of List - Similar two-pointer technique
• 189. Rotate Array - Rotate an array in place