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. Given the following recursive code to convert a binary number in a linked list to an integer, what is the final output when the linked list is 1 -> 0 -> 1?

easy

A. 3

B. 7

C. 6

D. 5

Solution

1. Step 1: Trace helper with node1 (val=1), acc=0

   acc = (0 << 1) | 1 = 1; recurse with node2

2. Step 2: Trace helper with node2 (val=0), acc=1

   acc = (1 << 1) | 0 = 2; recurse with node3

3. Step 3: Trace helper with node3 (val=1), acc=2

   acc = (2 << 1) | 1 = 5; recurse with None

4. Step 4: Trace helper with None, acc=5

   Return acc=5

5. Final Answer:

   Option D -> Option D

6. Quick Check:

   Binary 101 equals decimal 5 [OK]

Hint: Shift and OR accumulate bits from left to right [OK]

Common Mistakes:

• Off-by-one errors in shifting
• Confusing bitwise OR with addition
• Returning intermediate instead of final accumulated value

2. Given the following code for partitioning a linked list around value x = 3, and the input list: 1 -> 4 -> 2 -> 5, what is the final reordered list returned by the function?

easy

A. 1 -> 4 -> 2 -> 5

B. 1 -> 2 -> 4 -> 5

C. 2 -> 1 -> 4 -> 5

D. 4 -> 1 -> 2 -> 5

Solution

1. Step 1: Trace initial pointers with input 1 -> 4 -> 2 -> 5 and x=3

   Start with dummy -> 1 -> 4 -> 2 -> 5, less_tail and prev at dummy, current at 1.

2. Step 2: Process nodes

   Node 1 < 3, less_tail.next == current, move less_tail and prev forward. Node 4 >= 3, move prev and current forward. Node 2 < 3, less_tail.next != current, so remove 2 and insert after less_tail. Final list: 1 -> 2 -> 4 -> 5.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Nodes less than 3 appear first in original order, then others [OK]

Hint: Track less_tail and prev carefully to avoid skipping nodes [OK]

Common Mistakes:

• Swapping values instead of nodes
• Incorrect pointer updates causing lost nodes
• Assuming order changes within partitions

3. The following code attempts to implement the two stacks browser history. Identify the line containing the subtle bug that causes forward navigation to return outdated pages after visiting a new URL.

class BrowserHistory:
    def __init__(self, homepage: str):
        self.back_stack = [homepage]
        self.forward_stack = []

    def visit(self, url: str) -> None:
        self.back_stack.append(url)
        # Missing forward_stack.clear() here

    def back(self, steps: int) -> str:
        while steps > 0 and len(self.back_stack) > 1:
            self.forward_stack.append(self.back_stack.pop())
            steps -= 1
        return self.back_stack[-1]

    def forward(self, steps: int) -> str:
        while steps > 0 and self.forward_stack:
            self.back_stack.append(self.forward_stack.pop())
            steps -= 1
        return self.back_stack[-1]

medium

A. Line where back_stack.append(url) is called in visit

B. Line where forward_stack.clear() should be called but is missing in visit

C. Line where back_stack.pop() is called in back method

D. Line where forward_stack.pop() is called in forward method

Solution

1. Step 1: Identify visit method behavior

   Visit appends new URL but does not clear forward_stack, so forward history remains outdated.

2. Step 2: Understand impact on forward navigation

   Without clearing forward_stack, forward() returns stale pages that should have been discarded.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Clearing forward_stack on visit is essential to maintain correct forward history [OK]

Hint: Visit must clear forward history to avoid stale pages [OK]

Common Mistakes:

• Forgetting to clear forward stack on visit
• Incorrectly popping from back stack
• Mismanaging stack boundaries

4. What is the time complexity of the addAtTail operation in the optimal linked list implementation that maintains a tail pointer and size variable?

medium

A. O(n), because traversal is needed to find the tail

B. O(log n), because the list is balanced using sentinel nodes

C. O(1), because the tail pointer allows direct access to the last node

D. O(n), because updating the size requires traversal

Solution

1. Step 1: Identify operation steps

   addAtTail uses the tail pointer to append a new node directly without traversal.

2. Step 2: Analyze complexity

   Since tail pointer gives direct access, adding at tail is O(1). Size update is O(1) as it's a simple increment.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Tail pointer eliminates traversal, so addAtTail is constant time [OK]

Hint: Tail pointer enables O(1) tail insertions [OK]

Common Mistakes:

• Assuming traversal needed to find tail
• Confusing size update cost
• Thinking sentinel nodes balance list

5. Suppose the linked list with random pointers can contain cycles formed by next pointers (i.e., the list is not necessarily acyclic). Which modification to the optimal weaving approach is necessary to correctly copy such a list?

hard

A. Use a hash map to track visited nodes to avoid infinite loops during traversal.

B. Modify the separation step to break cycles before copying nodes.

C. No modification needed; the weaving approach works as is for cyclic lists.

D. Use recursion with memoization to handle cycles safely.

Solution

1. Step 1: Understand cycle impact on weaving approach

   The weaving approach assumes linear traversal; cycles cause infinite loops.

2. Step 2: Identify necessary modification

   Tracking visited nodes with a hash map prevents infinite loops by stopping revisits.

3. Step 3: Evaluate other options

   Breaking cycles before copying is complex; recursion risks stack overflow; no modification leads to infinite loop.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Hash map prevents infinite traversal in cyclic lists [OK]

Hint: Cycles require visited tracking to avoid infinite loops [OK]

Common Mistakes:

• Assuming acyclic list always
• Trying to break cycles before copying
• Using recursion without cycle detection