Bird
Raised Fist0
Interview Preplinked-list-advancedmediumAmazonGoogleFacebook

Odd Even Linked List

Choose your preparation mode4 modes available
▶
Steps
setup

Initialize / Setup

The linked list is created with nodes 1 → 2 → 3 → 4 → 5. The head pointer references node 1.

💡 Setting up the initial list is essential to visualize how nodes will be rearranged.
Line:head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
💡 The initial structure and head pointer are established for the recursive process.
📊
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

  1. Step 1: Initial state

    curr starts at node with val=1. First iteration: curr=1, no child, move to curr.next=2.
  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.
  3. Final Answer:

    Option B -> Option B
  4. 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

  1. 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.
  2. 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.
  3. Final Answer:

    Option D -> Option D
  4. 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

  1. 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).
  2. 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).
  3. Final Answer:

    Option A -> Option A
  4. 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

  1. Step 1: Identify the problem with recursion

    Deep recursion causes stack overflow for very long linked lists.
  2. 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.
  3. Step 3: Choose iterative approach

    Iterative bitwise accumulation uses constant stack space and linear time, handling large inputs safely.
  4. Final Answer:

    Option B -> Option B
  5. Quick Check:

    Iterative approach avoids recursion stack overflow [OK]
Hint: Iterative avoids recursion stack overflow on large inputs [OK]
Common Mistakes:
  • Relying on recursion limit increase which is unsafe
  • Assuming divide-and-conquer reduces recursion depth effectively
  • 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

  1. Step 1: Understand cycle problem

    Cycles via child pointers cause infinite loops if nodes are revisited during flattening.
  2. 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.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Visited set prevents infinite loops in cyclic structures [OK]
Hint: Cycle detection requires tracking visited nodes explicitly [OK]
Common Mistakes:
  • Assuming no cycles exist in input
  • Relying on recursion depth limits
  • Ignoring child pointers that create cycles
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard