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. Consider the following Python code that removes the 2nd node from the end of the list 1 -> 2 -> 3 -> 4 -> 5. What is the printed output after execution?

easy

A. 1 2 4 5

B. 1 2 3 5

C. 1 3 4 5

D. 2 3 4 5

Solution

1. Step 1: Trace recursion from end

   Recursion returns indices from the end: node 5 returns 1, node 4 returns 2, node 3 returns 3, etc.

2. Step 2: Identify node to remove

   When idx == n+1 = 3, node 3's next pointer skips node 4, effectively removing node 4.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Output matches list with 4 removed: 1 2 3 5 [OK]

Hint: Recursion index counts from end; remove node at idx = n+1 [OK]

Common Mistakes:

• Removing the node at idx == n instead of n+1
• Off-by-one errors in recursion index
• Confusing which node to skip

2. The following code attempts to detect a cycle in a circular array using the fast-slow pointer approach. Identify the line containing the subtle bug that causes incorrect cycle detection.

medium

A. Line with 'return true' inside while loop returns prematurely

B. Line with 'if slow == fast:' missing cycle length check

C. Line with 'direction = nums[i] > 0' incorrectly sets direction

D. Line with 'nums[marker] = 0' incorrectly marks visited elements

Solution

1. Step 1: Identify cycle detection condition

   The code returns true immediately when slow == fast, but does not check if cycle length > 1.

2. Step 2: Understand why self-loop is invalid

   Cycle of length 1 (self-loop) is invalid; must check if slow != next_index(slow) before returning true.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing cycle length check causes false positives [OK]

Hint: Check cycle length > 1 to avoid self-loop false positives [OK]

Common Mistakes:

• Returning true on self-loop cycles
• Mixing directions
• Not marking visited nodes

3. Identify the bug in the following code snippet for finding the duplicate number using Floyd's cycle detection:

medium

A. The initialization of slow and fast pointers is incorrect

B. The second while loop incorrectly updates fast pointer

C. The first while loop condition causes an infinite loop

D. The return statement should return fast instead of slow

Solution

1. Step 1: Examine the first while loop condition

   The loop condition is while slow != fast, but slow and fast are initialized to the same value, so the loop never runs, causing no intersection point found.

2. Step 2: Understand consequences

   Without the loop running, slow and fast pointers do not move, so the algorithm fails to detect the cycle and returns incorrect result or loops infinitely if code is modified.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Loop condition must allow first iteration; using while True with break is correct [OK]

Hint: First loop must run at least once to find intersection [OK]

Common Mistakes:

• Using while slow != fast before pointers move
• Incorrect pointer updates inside loops
• Returning wrong pointer at the end

4. If the linked list nodes can be reused multiple times (i.e., the list is cyclic or can be traversed repeatedly), which modification is necessary to the optimal palindrome check algorithm?

hard

A. No modification needed; the current algorithm works as is.

B. Use a stack to store first half values instead of reversing to avoid modifying the list.

C. Convert the list to an array to handle multiple traversals safely.

D. Restore the reversed second half to original order after comparison to preserve list structure.

Solution

1. Step 1: Understand reuse implications

   If nodes are reused or list is cyclic, modifying it breaks future traversals.

2. Step 2: Restore list after palindrome check

   Reversing second half in-place must be undone to preserve original list structure.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Restoring reversed half ensures list integrity for reuse [OK]

Hint: Always restore list after in-place reversal if list is reused [OK]

Common Mistakes:

• Ignoring list restoration causing side effects
• Switching to stack approach unnecessarily increasing space
• Assuming array conversion is always better

5. Suppose the problem is modified so that the linked list is circular (the last node points back to the head), and you need to remove the nth node from the end. Which approach correctly adapts to this scenario?

hard

A. First detect the cycle length by traversing until you return to the start, then remove the (length - n)th node using two pointers.

B. Use the same recursive backtracking approach without changes; it works for circular lists.

C. Break the cycle by setting the last node's next to None, then apply the standard two-pointer method.

D. Use a hash set to track visited nodes and remove the nth node from the end by counting backwards.

Solution

1. Step 1: Detect cycle length

   In a circular list, length is unknown; traverse until returning to start to find length.

2. Step 2: Use two pointers with known length

   Once length is known, use two pointers with gap n+1 to remove the target node safely.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Cycle length detection is necessary before removal [OK]

Hint: Must find cycle length before applying two-pointer removal [OK]

Common Mistakes:

• Applying recursion blindly on circular list causing infinite recursion
• Breaking cycle without restoring it, altering list structure
• Using hash sets unnecessarily increasing space