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.
Step 1/12
·Active fill★Answer cell
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/5)
1. 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
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.
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.
Final Answer:
Option B -> Option B
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
2. What is the time complexity of the in-place iterative flattening algorithm for a multilevel doubly linked list with total n nodes, considering the worst-case scenario where each node has a child list?
medium
A. O(n) amortized, since the total number of pointer updates and traversals sums to linear over all nodes.
B. O(n) because each node is visited a constant number of times during the flattening process.
C. O(n^2) because for each node with a child, we traverse its entire child list to find the tail.
D. O(n log n) due to repeated tail searches in nested child lists.
Solution
Step 1: Analyze tail-finding loop
Although tail is found by traversing child lists, each node is visited at most once as tail or curr.
Step 2: Amortized analysis
All next pointers are traversed linearly; tail searches do not overlap nodes multiple times, so total work is linear.
Final Answer:
Option A -> Option A
Quick Check:
Each node processed once, tail searches amortize to O(n) [OK]
Hint: Tail searches look nested but total visits are linear [OK]
Common Mistakes:
Assuming tail search is repeated fully for each child causing O(n^2)
Confusing amortized with worst-case per iteration
Ignoring that nodes are not revisited multiple times
3. What is the time and space complexity of the optimal in-place partition algorithm for a linked list of length n around value x?
medium
A. Time: O(n), Space: O(1)
B. Time: O(n), Space: O(n)
C. Time: O(n^2), Space: O(1)
D. Time: O(n log n), Space: O(1)
Solution
Step 1: Identify complexity of outer and inner loops
The algorithm traverses the list once, performing constant-time pointer operations per node, so time is O(n).
Step 2: Check if recursion stack adds extra space
No recursion or extra data structures are used; only a few pointers are maintained, so space is O(1).
Final Answer:
Option A -> Option A
Quick Check:
Single pass with constant pointers -> O(n) time and O(1) space [OK]
Hint: Single pass with pointer updates -> O(n) time, O(1) space [OK]
Common Mistakes:
Confusing with sorting complexity O(n log n)
Assuming extra arrays cause O(n) space
Mistaking pointer updates as nested loops causing O(n^2)
4. Consider the following buggy code snippet for reversing nodes in k-groups. Which line contains the subtle bug that can cause incorrect output when the list length is not a multiple of k?
medium
A. Line missing the check 'if count < k: break' after counting nodes
B. Line with 'group_next = kth.next' assignment
C. Line with 'while kth.next and count < k:' loop
D. Line with 'tmp.next = group_next' pointer update
Solution
Step 1: Identify missing boundary check
The code does not check if the remaining nodes are fewer than k before reversal.
Step 2: Consequence of missing check
Without 'if count < k: break', partial groups get reversed incorrectly, breaking problem constraints.
Final Answer:
Option A -> Option A
Quick Check:
Missing break causes partial group reversal [OK]
Hint: Always check group size before reversal [OK]
Common Mistakes:
Forgetting to break on partial group
Misplacing pointer updates
Assuming kth always valid
5. Suppose the linked list design is extended to allow negative indices in get and addAtIndex operations, where -1 refers to the last element, -2 to the second last, and so forth. Which modification correctly supports this feature without degrading average operation time complexity?
hard
A. Reject negative indices as invalid to keep implementation simple and efficient.
B. Traverse from tail backwards for negative indices to achieve O(1) access.
C. Use a doubly linked list instead of singly linked list to support backward traversal efficiently.
D. Modify get and addAtIndex to convert negative indices to positive by adding size, then proceed normally.
Solution
Step 1: Understand negative index semantics
Negative indices map to positive indices by adding the list size (e.g., -1 -> size-1).
Step 2: Implement index normalization
Convert negative indices to positive by adding size before performing normal operations, preserving O(n) traversal.
Step 3: Evaluate alternatives
Backward traversal from tail is not possible in singly linked list; doubly linked list adds complexity and space; rejecting negatives loses functionality.
Final Answer:
Option D -> Option D
Quick Check:
Index normalization preserves existing complexity and correctness [OK]
Hint: Normalize negative indices by adding size before operation [OK]
Common Mistakes:
Trying backward traversal in singly linked list
Switching to doubly linked list unnecessarily
Ignoring negative indices
Recommended
Ready to prove it?
Pass the test and this pattern moves unknownstrongwhile earning +1 Grip toward your certificate.