Reorder List (L0→Ln→L1→Ln-1)

▶

Steps

setup

Initialize pointers and start recursion

Set 'left' pointer to head (node 1) and 'stop' flag to False. Begin recursive helper function with 'right' at head (node 1).

💡 Initializing 'left' and 'stop' prepares for the recursive traversal from the front and back simultaneously.

Line:

left = head
stop = False
helper(head)

💡 The recursion will explore to the end of the list with 'right' while 'left' stays at the front initially.

traverse

Recursive call: move 'right' to node 2

'right' pointer moves to next node (2) in recursion call stack, going deeper to the end of the list.

💡 Recursion explores the list from the back by moving 'right' forward until it reaches null.

Line:

helper(right.next)  # right moves from 1 to 2

💡 The recursion stack builds up with 'right' moving forward, while 'left' remains at the front.

traverse

Recursive call: move 'right' to node 3

'right' pointer moves to node 3, continuing recursion deeper toward the list end.

💡 Each recursive call moves 'right' forward, building the call stack until the end is reached.

Line:

helper(right.next)  # right moves from 2 to 3

💡 The recursion depth increases, preparing to reorder nodes on unwind.

traverse

Recursive call: move 'right' to node 4 (end)

'right' pointer moves to last node (4), reaching the deepest recursion level.

💡 The recursion has reached the end of the list, ready to start reordering on unwind.

Line:

helper(right.next)  # right moves from 3 to 4

💡 At the deepest recursion, 'right' points to the last node, and reordering begins as recursion unwinds.

reconstruct

Unwind recursion: reorder nodes 1 and 4

On recursion return, 'left' is at node 1 and 'right' at node 4. Link node 1's next to node 4, and node 4's next to node 2. Move 'left' to node 2.

💡 This step connects the first and last nodes, starting the reorder pattern.

Line:

tmp = left.next
left.next = right
right.next = tmp
left = tmp

💡 The list is partially reordered: 1 → 4 → 2 → 3, with 'left' advanced to continue reordering.

compare

Unwind recursion: check stop condition at nodes 2 and 3

Now 'right' is at node 3 and 'left' at node 2. Check if 'left' equals 'right' or 'left.next' equals 'right' to stop reordering.

💡 Stopping condition prevents cycles and overlapping links.

Line:

if left == right or left.next == right:
    right.next = None
    stop = True
    return

💡 The algorithm detects the middle and stops to avoid cycles.

prune

Stop recursion and finalize list

Set 'right.next' to null to break the chain and prevent cycles. Set stop flag to True to end recursion.

💡 Breaking the link here ensures the reordered list ends correctly.

Line:

right.next = None
stop = True

💡 The list is now properly terminated after reordering.

reconstruct

Recursion fully unwound, reordered list ready

All recursive calls return. The list is reordered as 1 → 4 → 2 → 3 with no cycles.

💡 The recursion completes, and the reordered list is fully connected.

Line:

return from helper calls

💡 The recursive approach successfully reordered the list in-place.

traverse

Traverse reordered list to read output: start at node 1

Traverse the reordered list from head to print values in order: starting at node 1.

💡 Reading the list confirms the reorder was successful.

Line:

curr = head
while curr:
    print(curr.val)
    curr = curr.next

💡 The output matches the expected reordered sequence.

traverse

Traverse reordered list: move 'curr' to node 4

Move 'curr' pointer from node 1 to node 4, reading the next value in the reordered list.

💡 Stepwise traversal shows the final order clearly.

Line:

curr = curr.next  # move from node 1 to node 4

💡 The traversal confirms the next node in the reordered list is node 4.

traverse

Traverse reordered list: move 'curr' to node 2

Move 'curr' pointer from node 4 to node 2, continuing traversal of the reordered list.

💡 Stepwise traversal confirms the order of nodes in the reordered list.

Line:

curr = curr.next  # move from node 4 to node 2

💡 The traversal confirms the next node in the reordered list is node 2.

traverse

Traverse reordered list: move 'curr' to node 3 (end)

Move 'curr' pointer from node 2 to node 3, reaching the end of the reordered list.

💡 Final step of traversal confirms the full reordered list output.

Line:

curr = curr.next  # move from node 2 to node 3

💡 The traversal confirms the final reordered list is [1,4,2,3].

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

def reorderList(head):
    def helper(right):
        nonlocal left, stop
        if not right:
            return  # STEP 1: base case, end recursion
        helper(right.next)  # STEP 2-4: recurse to end
        if stop:
            return  # STEP 7: stop if reordering done
        if left == right or left.next == right:
            right.next = None  # STEP 6-7: stop condition, break cycle
            stop = True
            return
        tmp = left.next  # STEP 5: save next node after left
        left.next = right  # STEP 5: link left to right
        right.next = tmp  # STEP 5: link right to tmp
        left = tmp  # STEP 5: move left forward

    left = head  # STEP 1: initialize left pointer
    stop = False  # STEP 1: initialize stop flag
    helper(head)  # STEP 1: start recursion

# Driver code
if __name__ == '__main__':
    n4 = ListNode(4)
    n3 = ListNode(3, n4)
    n2 = ListNode(2, n3)
    n1 = ListNode(1, n2)
    reorderList(n1)
    curr = n1
    while curr:
        print(curr.val, end=' ')
        curr = curr.next
    print()

📊

Reorder List (L0→Ln→L1→Ln-1) - Watch the Algorithm Execute, Step by Step

Watching each pointer move and link change helps you understand how recursion unwinds and how nodes are reordered without extra space.

advance

1

→

2

→

3

→

4

advance

1

→

2

→

3

→

4

advance

1

→

2

→

3

→

4

advance

1

→

2

→

3

→

4

connect

1

→

2

→

3

→

4

compare

1

→

2

→

3

→

4

detach

1

→

2

→

3

→

4

none

1

→

2

→

3

→

4

traverse

1

→

2

→

3

→

4

Result: [1]

traverse

1

→

2

→

3

→

4

Result: [1, 4]

traverse

1

→

2

→

3

→

4

Result: [1, 4, 2]

traverse

1

→

2

→

3

→

4

Result: [1, 4, 2, 3]

Key Takeaways

✓ The recursive approach uses a front pointer and a back pointer moving inward simultaneously to reorder the list in place.

This insight is hard to see from code alone because recursion hides the back pointer movement in the call stack.

✓ Stopping conditions prevent cycles by detecting when pointers meet or cross in the middle of the list.

Understanding when and why to stop is clearer when watching the pointers and links change step-by-step.

✓ The reordering rewires next pointers alternately from front and back nodes, preserving list integrity without extra space.

Seeing the exact pointer updates helps grasp how the list is reconstructed without losing nodes.

Practice

1. You are given an array of n + 1 integers where each integer is between 1 and n (inclusive). There is exactly one duplicate number but it could be repeated multiple times. Which approach guarantees finding the duplicate in O(n) time and O(1) space without modifying the input array?

easy

A. Sort the array and then scan for consecutive duplicates

B. Use two pointers moving at different speeds to detect a cycle in the array values

C. Use a hash set to track seen numbers and return the first duplicate

D. Use nested loops to compare every pair of elements

Solution

1. Step 1: Understand the problem constraints

   The array contains n+1 integers with values from 1 to n, guaranteeing at least one duplicate. The input cannot be modified and extra space must be O(1).

2. Step 2: Identify the approach that fits constraints

   Sorting modifies the array, hash sets use extra space, nested loops are O(n²). Floyd's cycle detection uses two pointers at different speeds to find a cycle in O(n) time and O(1) space without modifying the array.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two-pointer cycle detection fits all constraints [OK]

Hint: Cycle detection fits O(n) time and O(1) space [OK]

Common Mistakes:

• Assuming sorting is allowed despite input constraints
• Believing hash sets use constant space
• Thinking nested loops are efficient enough

2. You are given a problem where you repeatedly transform a number by replacing it with the sum of the squares of its digits. The goal is to determine if this process eventually reaches 1 or falls into a repeating cycle. Which algorithmic approach is best suited to efficiently detect cycles in this implicit sequence without extra space?

easy

A. Dynamic Programming with memoization to store intermediate results

B. Breadth-First Search (BFS) to explore all possible transformations

C. Greedy approach to pick the next number with the smallest digit sum

D. Floyd's Cycle Detection (Fast and Slow Pointers) to detect cycles in sequences

Solution

1. Step 1: Understand the problem as detecting cycles in a sequence generated by a function

   The problem involves repeatedly applying a function to a number to generate a sequence. Detecting if this sequence reaches 1 or cycles indefinitely is a classic cycle detection problem.

2. Step 2: Identify Floyd's Cycle Detection as the optimal approach

   Floyd's fast and slow pointers efficiently detect cycles in sequences without extra space, unlike DP or BFS which require additional memory or are not suited for implicit sequences.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Cycle detection in implicit sequences -> Floyd's algorithm [OK]

Hint: Cycle detection in sequences -> Floyd's fast-slow pointers [OK]

Common Mistakes:

• Confusing cycle detection with DP or BFS approaches

3. Consider the following code that detects a cycle by marking nodes as visited. Given the linked list: 1 -> 2 -> 3 -> 4 -> 2 (cycle back to node with value 2), what is the output of hasCycle(node1)?

easy

A. true

B. false

C. null

D. Runtime error due to infinite loop

Solution

1. Step 1: Trace the traversal and marking of nodes

   Start at node1 (visited=false), mark visited=true, move to node2. Repeat for node2 and node3. When reaching node4, mark visited=true and move to node2 again, which is already visited.

2. Step 2: Detect cycle when revisiting node2

   Since node2.visited is true, the function returns true indicating a cycle.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Cycle detected correctly by visited flag [OK]

Hint: Cycle detected when revisiting a marked node [OK]

Common Mistakes:

• Assuming no cycle due to missing pointer update
• Confusing return values

4. What is the time and space complexity of Floyd's cycle detection algorithm used to find the start of a cycle in a linked list of length n?

medium

A. Time: O(n), Space: O(1)

B. Time: O(n^2), Space: O(1)

C. Time: O(n), Space: O(n)

D. Time: O(n log n), Space: O(1)

Solution

1. Step 1: Analyze time complexity of pointer movements

   Fast pointer moves twice as fast as slow pointer, so they meet in O(n) steps, and locating cycle start also takes O(n) steps, total O(n).

2. Step 2: Analyze space complexity

   Only a fixed number of pointers are used, no extra data structures, so space is O(1).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time and constant space are standard for Floyd's algorithm [OK]

Hint: Two pointers traverse list linearly, no extra space needed [OK]

Common Mistakes:

• Confusing space with hash set approach
• Assuming quadratic time due to nested loops
• Mistaking recursion stack space

5. The following code attempts to remove the nth node from the end of a singly linked list. Identify the line containing the subtle bug that causes incorrect behavior when removing the head node.

medium

A. Line 12: recurse(head)

B. Line 9: node.next = node.next.next

C. Line 3: def recurse(node):

D. Line 13: return head

Solution

1. Step 1: Understand dummy node role

   Dummy node is needed to handle removal of the head node safely.

2. Step 2: Identify missing dummy usage

   Calling recurse on head directly skips dummy, so removing head node breaks list or returns wrong head.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing dummy node causes incorrect removal of head [OK]

Hint: Always use dummy node to handle head removal edge case [OK]

Common Mistakes:

• Not using dummy node causing null pointer or wrong head
• Incorrectly unlinking nodes causing list corruption
• Off-by-one errors in recursion index