Rotate List

▶

Steps

setup

Initialize length and tail

Start with length = 1 and tail pointing to head (node with value 1). We prepare to find the list length and tail node.

💡 Knowing the list length and tail is essential to handle rotation correctly and to form the circular list later.

Line:

length = 1
tail = head

💡 Initial setup to traverse the list and count nodes.

setup

Traverse to find tail and length (node 2)

Move tail pointer from node 1 to node 2 and increment length to 2.

💡 Each move advances tail to the next node, counting nodes to find the list length.

Line:

tail = tail.next
length += 1

💡 Tail moves forward to find the last node; length counts nodes.

setup

Traverse to find tail and length (node 3)

Move tail pointer from node 2 to node 3 and increment length to 3.

💡 Continuing traversal to find the last node and total length.

Line:

tail = tail.next
length += 1

💡 Tail advances; length counts nodes.

setup

Traverse to find tail and length (node 4)

Move tail pointer from node 3 to node 4 and increment length to 4.

💡 Continuing traversal to find the last node and total length.

Line:

tail = tail.next
length += 1

💡 Tail advances; length counts nodes.

setup

Traverse to find tail and length (node 5)

Move tail pointer from node 4 to node 5 and increment length to 5. Tail now points to the last node.

💡 Traversal complete; length and tail are known.

Line:

tail = tail.next
length += 1

💡 Tail points to last node; length is total nodes count.

setup

Calculate effective rotation k

Calculate k = k % length to handle cases where k >= length. Here k=2 % 5 = 2, so rotation remains 2.

💡 Modulo ensures rotation does not exceed list length, avoiding unnecessary full rotations.

Line:

k = k % length

💡 Effective rotation steps are within list length.

expand

Make the list circular

Connect tail.next to head, forming a circular linked list to facilitate rotation.

💡 Forming a cycle allows easy pointer movement without worrying about list end.

Line:

tail.next = head  # make circular

💡 List is now circular; tail points back to head.

traverse

Advance fast pointer k steps ahead

Move fast pointer from head (node 1) forward 2 steps to node 3.

💡 Fast pointer leads slow pointer by k nodes to find new tail after traversal.

Line:

fast = head
for _ in range(k):
    fast = fast.next

💡 Fast pointer is now k nodes ahead of slow pointer.

traverse

Initialize slow pointer at head

Set slow pointer to head (node 1) to start moving both pointers together.

💡 Slow pointer will follow fast pointer until fast reaches tail to find new tail.

Line:

slow = head

💡 Slow pointer ready to move in tandem with fast pointer.

traverse

Move slow and fast pointers forward (step 1)

Move slow from node 1 to 2 and fast from node 3 to 4, advancing both pointers one step.

💡 Moving both pointers keeps their distance; when fast reaches tail, slow is at new tail.

Line:

while fast != tail:
    slow = slow.next
    fast = fast.next

💡 Pointers advance together maintaining gap.

traverse

Move slow and fast pointers forward (step 2)

Move slow from node 2 to 3 and fast from node 4 to 5, advancing both pointers one step. Fast now points to tail.

💡 When fast reaches tail, slow points to new tail node for rotation.

Line:

while fast != tail:
    slow = slow.next
    fast = fast.next

💡 Slow pointer is at new tail after rotation.

prune

Set new head and break the circle

Set new_head to slow.next (node 4), then break the circle by setting slow.next to None.

💡 Breaking the circle at new tail finalizes the rotated list.

Line:

new_head = slow.next
slow.next = None

💡 New head is the node after new tail; list is no longer circular.

reconstruct

Return new head of rotated list

Return new_head (node 4) as the head of the rotated list [4,5,1,2,3].

💡 The rotated list starts at new_head, reflecting the rotation by k steps.

Line:

return new_head

💡 Rotation complete; new head points to rotated list start.

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  # STEP 1: Handle trivial cases
    length = 1
    tail = head  # STEP 2: Initialize length and tail
    while tail.next:
        tail = tail.next  # STEP 3: Move tail forward
        length += 1  # STEP 3: Increment length
    k = k % length  # STEP 4: Modulo k by length
    if k == 0:
        return head  # STEP 5: If no rotation needed
    tail.next = head  # STEP 6: Make list circular
    fast = head
    for _ in range(k):
        fast = fast.next  # STEP 7: Move fast k steps ahead
    slow = head  # STEP 8: Initialize slow pointer
    while fast != tail:
        slow = slow.next  # STEP 9: Move slow forward
        fast = fast.next  # STEP 9: Move fast forward
    new_head = slow.next  # STEP 10: New head is after slow
    slow.next = None  # STEP 10: Break the circle
    return new_head  # STEP 11: Return rotated list head

# Driver code
if __name__ == '__main__':
    nodes = [ListNode(i) for i in range(1,6)]
    for i in range(4):
        nodes[i].next = nodes[i+1]
    rotated = rotateRight(nodes[0], 2)
    curr = rotated
    while curr:
        print(curr.val, end=' ')
        curr = curr.next
    print()

📊

Rotate List - Watch the Algorithm Execute, Step by Step

Watching each pointer move and link change helps you understand how rotation is achieved without extra space or copying nodes.

advance

1

→

2

→

3

→

4

→

5

advance

1

→

2

→

3

→

4

→

5

advance

1

→

2

→

3

→

4

→

5

advance

1

→

2

→

3

→

4

→

5

advance

1

→

2

→

3

→

4

→

5

prune

1

→

2

→

3

→

4

→

5

connect

1

→

2

→

3

→

4

→

5

advance

1

→

2

→

3

→

4

→

5

advance

1

→

2

→

3

→

4

→

5

advance

1

→

2

→

3

→

4

→

5

compare

1

→

2

→

3

→

4

→

5

detach

1

→

2

→

3

→

4

→

5

return

4

→

5

→

1

→

2

→

3

Result: [4, 5, 1, 2, 3]

Key Takeaways

✓ Forming a circular linked list simplifies rotation by allowing pointer movement without worrying about list ends.

This insight is hard to see from code alone because the circular link is a subtle but powerful trick.

✓ Advancing the fast pointer k steps ahead creates a fixed gap that helps identify the new tail after traversal.

Visualizing pointer gaps clarifies why this approach finds the rotation point efficiently.

✓ Breaking the circle at the slow pointer's next node finalizes the rotated list and sets the new head.

Understanding where to break the link is crucial and is easier to grasp when watching the pointers move.

Practice

1. Given two singly linked lists that may or may not intersect, which approach guarantees finding the intersection node in O(m + n) time and O(1) space without modifying the lists?

easy

A. Store all nodes of the first list in a hash set, then check each node of the second list against the set.

B. Use nested loops to compare every node in the first list with every node in the second list.

C. Use two pointers starting at each list head, switching heads when reaching the end, to equalize path lengths and find the intersection.

D. Sort both lists by node values and then scan simultaneously to find matching values.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the intersection node without extra space and in linear time.

2. Step 2: Evaluate approaches

   Nested loops (B) are O(m*n), hash set (C) uses extra space, sorting (D) is invalid as node values may not be unique and sorting modifies lists. The two-pointer approach (A) equalizes path lengths by switching heads, ensuring both pointers traverse equal total lengths and meet at the intersection or end.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two-pointer approach is O(m+n) time and O(1) space [OK]

Hint: Two pointers switching heads equalize lengths [OK]

Common Mistakes:

• Confusing node values with node references
• Using extra space unnecessarily
• Assuming sorting helps with intersection

2. Consider the following Python code for merging two sorted linked lists in-place:

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

def mergeTwoLists(l1, l2):
    if not l1:
        return l2
    if not l2:
        return l1
    if l1.val > l2.val:
        l1, l2 = l2, l1
    head = l1
    while l1 and l2:
        prev = None
        while l1 and l1.val <= l2.val:
            prev = l1
            l1 = l1.next
        prev.next = l2
        l1, l2 = l2, l1
    return head

# Input lists:
# l1: 1 -> 3 -> 5
# l2: 2 -> 4

merged_head = mergeTwoLists(l1, l2)

What is the value of the node pointed to by prev after the first inner while loop iteration inside the outer while loop?

easy

A. Node with value 3

B. Node with value 5

C. Node with value 1

D. Node with value 2

Solution

1. Step 1: Trace the inner while loop with initial lists

   Initially, l1 points to 1, l2 points to 2. The inner loop advances l1 while l1.val <= l2.val: - l1=1 (<=2), prev=1, l1 moves to 3 - l1=3 (>2), loop stops

2. Step 2: Identify prev after loop

   Prev points to node with value 1 after the inner loop ends, which is the last node with value less than or equal to l2.val.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Prev points to last l1 node ≤ current l2 node [OK]

Hint: Prev points to last l1 node ≤ current l2 node [OK]

Common Mistakes:

• Assuming prev points to node with value 3 after first inner loop
• Confusing l1 and l2 pointers after swap
• Forgetting that prev updates inside inner loop

3. The following code attempts to reverse nodes in k-groups but contains a subtle bug. Which line causes the bug that leads to incorrect list connections after reversal?

medium

A. Line: prev = reverseLinkedList(group_prev.next, k)

B. Line: tail.next = group_prev.next # Bug here

C. Line: if count < k: break

D. Line: group_prev = dummy

Solution

1. Step 1: Understand the role of tail.next after reversal

   After reversing k nodes, tail (original head) should point to group_next to maintain list continuity.

2. Step 2: Identify the incorrect pointer assignment

   Assigning tail.next = group_prev.next reconnects tail to the old head, causing cycles or broken links.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct line should be tail.next = group_next [OK]

Hint: Tail must connect to next group's head, not old head [OK]

Common Mistakes:

• Forgetting to update tail.next to group_next
• Misassigning pointers causing cycles

4. Suppose the problem is extended so that the input linked lists can be reused multiple times in different additions without modification. Which modification to the optimal recursive solution is necessary to ensure correctness and input integrity?

hard

A. Use stacks to simulate reverse traversal without modifying input lists or copying.

B. Create deep copies of input lists before padding and addition to avoid modifying original lists.

C. Modify the recursive function to add digits without padding or copying.

D. Reverse the input lists in-place before addition to simplify logic.

Solution

1. Step 1: Understand input reuse constraint

   Input lists must remain unmodified for reuse, so in-place reversal or padding that changes nodes is disallowed.

2. Step 2: Identify approach preserving input integrity

   Using stacks to simulate reverse traversal reads digits from least significant to most significant without modifying or copying the lists.

3. Step 3: Compare alternatives

   Reversing in-place breaks input reuse; copying is expensive; recursion without padding fails alignment.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Stacks preserve input and allow correct addition [OK]

Hint: Stacks simulate reverse without input mutation [OK]

Common Mistakes:

• Reversing input lists modifies them
• Copying inputs is costly and unnecessary
• Ignoring alignment leads to wrong sums

5. Suppose the digits in the input linked lists are stored in forward order (most significant digit first). Which modification to the in-place iterative addition algorithm is necessary to correctly add the two numbers?

hard

A. Traverse both lists once, adding digits directly without reversing, handling carry forward.

B. Create new nodes for the sum since in-place modification is impossible with forward order.

C. Use recursion to add digits from head to tail, passing carry backward.

D. Reverse both input lists, apply the in-place addition, then reverse the result list back.

Solution

1. Step 1: Understand forward order challenge

   Digits stored most significant first require addition from tail to head to handle carry properly.

2. Step 2: Reverse input lists

   Reversing both lists converts them to reverse order, allowing reuse of the in-place addition algorithm.

3. Step 3: Reverse result list

   After addition, reverse the result to restore forward order.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Reversing lists enables correct carry handling in forward order [OK]

Hint: Reverse lists to reuse reverse-order addition logic [OK]

Common Mistakes:

• Trying to add forward order lists without reversing
• Assuming carry can be handled left-to-right easily
• Creating new lists unnecessarily