💡 Odd list is built by linking current odd node to previously returned odd list head.
traverse
Find tail of odd list
Starting from odd_head (node 1), iterate to find the last node in odd list (node 5).
💡 Finding the tail is necessary to connect odd and even lists.
Line:curr = odd_head
while curr and curr.next:
curr = curr.next
💡 Traversal locates the last odd node to link even list after it.
connect
Connect tail of odd list to head of even list
Set curr.next (node 5's next) to even_head (node 2), linking odd and even lists.
💡 This step merges the two separated lists into the final reordered list.
Line:if curr:
curr.next = even_head
💡 Connecting odd tail to even head completes the odd-even rearrangement.
reconstruct
Return final reordered list head
Return odd_head (node 1) as the head of the reordered list 1 → 3 → 5 → 2 → 4.
💡 The reordered list head is returned for further use or output.
Line:return odd_head
💡 The reordered list starts at the original head, now rearranged by odd-even positions.
traverse
Traverse final list to collect output
Traverse from head (node 1) through next pointers to collect values in order: 1, 3, 5, 2, 4.
💡 Traversing the final list confirms the correct odd-even rearrangement.
Line:curr = new_head
while curr:
res.append(curr.val)
curr = curr.next
💡 Traversal verifies the final linked list order matches expected output.
traverse
Continue traversal: node 3
Move pointer to node 3, append value 3 to output list.
💡 Stepwise traversal shows output list building incrementally.
Line:res.append(curr.val)
curr = curr.next
💡 Output list grows as traversal proceeds through reordered nodes.
traverse
Continue traversal: node 5
Move pointer to node 5, append value 5 to output list.
💡 Traversal continues to confirm all nodes are visited in order.
Line:res.append(curr.val)
curr = curr.next
💡 Traversal confirms odd nodes appear first in output.
traverse
Continue traversal: node 2
Move pointer to node 2, append value 2 to output list.
💡 Traversal now visits even nodes after odd nodes.
Line:res.append(curr.val)
curr = curr.next
💡 Even nodes follow odd nodes in the output list.
traverse
Finish traversal: node 4 and end
Move pointer to node 4, append value 4 to output list, then reach null ending traversal.
💡 Traversal completes, confirming final output list matches expected.
Line:res.append(curr.val)
curr = curr.next
💡 Traversal confirms final reordered list is [1, 3, 5, 2, 4].
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def oddEvenList(head):
def helper(node, index):
if not node: # STEP 7
return (None, None) # (odd_head, even_head)
odd_head, even_head = helper(node.next, index + 1) # STEP 2-6
if index % 2 == 1: # STEP 8,10,12
node.next = odd_head
return (node, even_head)
else: # STEP 9,11
node.next = even_head
return (odd_head, node)
odd_head, even_head = helper(head, 1) # STEP 1
curr = odd_head # STEP 13
while curr and curr.next:
curr = curr.next
if curr: # STEP 14
curr.next = even_head
return odd_head # STEP 15
if __name__ == '__main__':
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5))))) # STEP 1
new_head = oddEvenList(head)
curr = new_head
res = []
while curr: # STEP 16-20
res.append(curr.val)
curr = curr.next
print(res) # Expected: [1,3,5,2,4]
📊
Odd Even Linked List - Watch the Algorithm Execute, Step by Step
Watching each recursive call and pointer reassignment reveals how the list is split and merged without extra space.
Step 1/20
·Active fill★Answer cell
advance
1
→
2
→
3
→
4
→
5
traverse
1
→
2
→
3
→
4
→
5
traverse
1
→
2
→
3
→
4
→
5
traverse
1
→
2
→
3
→
4
→
5
traverse
1
→
2
→
3
→
4
→
5
traverse
1
→
2
→
3
→
4
→
5
traverse
1
→
2
→
3
→
4
→
5
connect
5
Result:
Odd head:5
Even head:null
connect
5
→
4
Result:
Odd head:5
Even head:4
connect
3
→
5
→
4
Result:
Odd head:3
Even head:4
connect
3
→
5
→
2
→
4
Result:
Odd head:3
Even head:2
connect
1
→
3
→
5
→
2
→
4
Result:
Odd head:1
Even head:2
traverse
1
→
3
→
5
→
2
→
4
Result:
Odd head:1
Even head:2
connect
1
→
3
→
5
→
2
→
4
advance
1
→
3
→
5
→
2
→
4
traverse
1
→
3
→
5
→
2
→
4
Result: [1]
traverse
1
→
3
→
5
→
2
→
4
Result: [1, 3]
traverse
1
→
3
→
5
→
2
→
4
Result: [1, 3, 5]
traverse
1
→
3
→
5
→
2
→
4
Result: [1, 3, 5, 2]
traverse
1
→
3
→
5
→
2
→
4
Result: [1, 3, 5, 2, 4]
Key Takeaways
✓ The recursive approach separates odd and even nodes by index during the call stack unwind, building two lists simultaneously.
This insight is hard to see from code alone because recursion hides the order of operations until return.
✓ Odd nodes are linked to the previously returned odd list head, and even nodes to the even list head, effectively reversing the list during recursion.
Visualizing pointer reassignments clarifies how the list is rebuilt in correct order.
✓ The final step connects the tail of the odd list to the head of the even list, merging the two sublists into the final reordered list.
Understanding this merge is key to grasping how the algorithm produces the final output.
Practice
(1/5)
1. Given the following code snippet implementing the in-place iterative flattening of a multilevel doubly linked list, and the input list: 1 <-> 2 <-> 3, where node 2 has a child list 4 <-> 5, what is the value of curr.val after the first iteration of the outer while loop?
easy
A. 1
B. 4
C. 2
D. 3
Solution
Step 1: Initial state
curr starts at node with val=1. First iteration: curr=1, no child, move to curr.next=2.
Step 2: First iteration with child
curr=2 has child list starting at 4. The code finds tail=5, connects tail.next to curr.next (3), updates pointers, sets curr.next=4, child.prev=2, curr.child=None, then moves curr=curr.next=4.
Final Answer:
Option B -> Option B
Quick Check:
After first iteration, curr moves to child node 4 [OK]
Hint: After splicing child, curr moves to child's head node [OK]
Common Mistakes:
Assuming curr stays at original node after splicing
Forgetting to move curr to next after flattening
Confusing tail with child head
2. Given the following code snippet for reversing nodes in k-groups, and the input list 1->2->3->4 with k=2, what is the value of group_prev.next.val after the first group reversal?
easy
A. 4
B. 1
C. 3
D. 2
Solution
Step 1: Trace first group reversal
Input list: 1->2->3->4, k=2. First group is nodes 1 and 2. After reversal, group becomes 2->1.
Step 2: Identify group_prev.next after reversal
Initially, group_prev is dummy pointing to 1. After reversal, group_prev.next points to 2, the new head of reversed group.
Final Answer:
Option D -> Option D
Quick Check:
First group's head after reversal is node with value 2 [OK]
Hint: First group's head after reversal is the kth node [OK]
Common Mistakes:
Confusing original head with new head after reversal
Off-by-one in counting nodes
Misunderstanding pointer updates
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. Suppose the linked list can be extremely long (millions of nodes), causing recursion stack overflow in the recursive solution. Which modification is the best to handle this scenario efficiently?
hard
A. Increase the recursion limit to accommodate the large linked list depth.
B. Switch to an iterative approach that accumulates the decimal value using bit shifts.
C. Use a divide-and-conquer recursive approach to reduce recursion depth.
D. Convert the linked list to a string first, then parse the binary string to integer.
Solution
Step 1: Identify the problem with recursion
Deep recursion causes stack overflow for very long linked lists.
Step 2: Evaluate alternatives
Increasing recursion limit is risky and platform-dependent; divide-and-conquer adds complexity without reducing total depth; string conversion is inefficient.
Step 3: Choose iterative approach
Iterative bitwise accumulation uses constant stack space and linear time, handling large inputs safely.
Using string conversion which is inefficient for large inputs
5. Suppose the multilevel doubly linked list can contain cycles via child pointers (i.e., a child pointer may point to an ancestor node). Which modification to the in-place iterative flattening algorithm correctly handles this scenario without infinite loops?
hard
A. Ignore cycles since the algorithm naturally terminates when curr is null.
B. Remove all child pointers before flattening to break cycles.
C. Use recursion with a depth limit to avoid infinite recursion.
D. Add a visited set to track nodes already processed and skip nodes if revisited.
Solution
Step 1: Understand cycle problem
Cycles via child pointers cause infinite loops if nodes are revisited during flattening.
Step 2: Evaluate solutions
Ignoring cycles (A) causes infinite loops. Removing child pointers (B) loses data. Recursion with depth limit (C) is unreliable. Tracking visited nodes (D) prevents revisiting and infinite loops.
Final Answer:
Option D -> Option D
Quick Check:
Visited set prevents infinite loops in cyclic structures [OK]