Bird
Raised Fist0
Interview Preplinked-list-advancedmediumAmazonGoogleFacebook

Odd Even Linked List

Choose your preparation mode4 modes available
</>
IDE
def oddEvenList(head: Optional[ListNode]) -> Optional[ListNode]:public ListNode oddEvenList(ListNode head)ListNode* oddEvenList(ListNode* head)function oddEvenList(head)
def oddEvenList(head):
    # Write your solution here
    pass
class Solution {
    public ListNode oddEvenList(ListNode head) {
        // Write your solution here
        return head;
    }
}
#include <vector>
using namespace std;

ListNode* oddEvenList(ListNode* head) {
    // Write your solution here
    return head;
}
function oddEvenList(head) {
    // Write your solution here
}
0/10
Common Bugs to Avoid
Wrong: [1, 2, 3, 4, 5]No rearrangement done; code returns input as is.✅ Implement logic to separate odd and even nodes and link odd list to even list.
Wrong: [1, 3, 5, 4, 2]Even nodes reversed or order not preserved.✅ Maintain even nodes in original order by linking them as encountered.
Wrong: [2, 1]Swapped odd and even nodes or indexing starts at 0 incorrectly.✅ Index nodes starting at 1 and separate odd and even accordingly.
Wrong: [1, 2, 1, 2, 2, 1]Grouping by node value instead of position parity.✅ Group nodes strictly by their position index parity, not by value.
Wrong: Timeout or no outputInefficient algorithm with O(n^2) or worse complexity.✅ Use a single pass O(n) algorithm with two pointers and O(1) extra space.
✓
Test Cases
t1_01basic
Input{"head":[1,2,3,4,5]}
Expected[1,3,5,2,4]

Nodes at odd positions 1,3,5 come first, followed by even positions 2,4.

t1_02basic
Input{"head":[2,1,3,5,6,4,7]}
Expected[2,3,7,1,5,4,6]

Odd indices nodes 2,3,7 followed by even indices nodes 1,5,4,6.

t2_01edge
Input{"head":[]}
Expected[]

Empty list input returns empty list.

t2_02edge
Input{"head":[10]}
Expected[10]

Single node list returns same list unchanged.

t2_03edge
Input{"head":[7,7,7,7]}
Expected[7,7,7,7]

All nodes have same value; order preserved with odd nodes first then even nodes.

t2_04edge
Input{"head":[1,2]}
Expected[1,2]

Two node list; odd node followed by even node.

t3_01corner
Input{"head":[1,2,3,4,5,6]}
Expected[1,3,5,2,4,6]

Even number of nodes; odd nodes 1,3,5 followed by even nodes 2,4,6.

t3_02corner
Input{"head":[1,2,3,4,5,6,7,8,9]}
Expected[1,3,5,7,9,2,4,6,8]

Odd nodes 1,3,5,7,9 followed by even nodes 2,4,6,8; tests off-by-one errors.

t3_03corner
Input{"head":[1,2,2,1,1,2]}
Expected[1,2,1,2,2,1]

Tests confusion between 0/1-based indexing and value-based grouping.

t4_01performance
Input{"head":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100]}
⏱ Performance - must finish in 2000ms

n=100 nodes; O(n) time complexity required to complete within 2 seconds.

Practice

(1/5)
1. You are given a singly linked list where each node contains a binary digit (0 or 1). The linked list represents a binary number with the head as the most significant bit. Which approach guarantees an optimal solution to convert this linked list to its decimal integer value?
easy
A. Iteratively accumulate the decimal value by shifting the current value left by 1 and OR-ing with the current node's bit.
B. Use a greedy approach to pick bits that maximize the decimal value at each step.
C. Traverse the list to build a string of bits, then parse the string as a binary number.
D. Apply dynamic programming to store intermediate decimal values for sublists.

Solution

  1. Step 1: Understand the problem constraints

    The linked list represents a binary number with the head as the most significant bit, so the decimal value can be built by processing bits from left to right.
  2. Step 2: Identify the optimal approach

    Iteratively shifting the accumulated value left by 1 and OR-ing with the current bit correctly builds the decimal value in O(n) time and O(1) space, without extra string conversions or complex DP.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Bitwise accumulation matches binary to decimal conversion [OK]
Hint: Bitwise accumulation is optimal for binary to decimal conversion [OK]
Common Mistakes:
  • Using string concatenation then parsing wastes time and space
  • Greedy approaches don't apply to binary number conversion
  • Dynamic programming is unnecessary overhead here
2. Given the following code snippet for splitting a linked list into k=3 parts, and the input list 1->2->3->4, what is the returned list of parts (values only)?
easy
A. [[1, 2], [3, 4], []]
B. [[1, 2], [3], [4]]
C. [[1, 2], [3], [4, None]]
D. [[1], [2], [3, 4]]

Solution

  1. Step 1: Calculate total nodes and part sizes

    Total nodes = 4, k = 3, so part_size = 1, remainder = 1. First remainder parts get one extra node.
  2. Step 2: Assign nodes to parts

    Part 0 size = 2 nodes (1,2), Part 1 size = 1 node (3), Part 2 size = 1 node (4). The returned parts are [[1,2],[3],[4]].
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Sum of parts equals original list length and sizes differ by at most one [OK]
Hint: Remainder nodes assigned to first parts -> first part larger [OK]
Common Mistakes:
  • Assigning remainder nodes to last parts
  • Off-by-one in part sizes
  • Returning fewer than k parts
3. 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

  1. 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.
  2. Step 2: Amortized analysis

    All next pointers are traversed linearly; tail searches do not overlap nodes multiple times, so total work is linear.
  3. Final Answer:

    Option A -> Option A
  4. 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
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 partition problem is modified so that nodes can be reused multiple times (e.g., the list represents a multiset with unlimited copies). Which modification to the optimal in-place partition algorithm correctly handles this scenario without breaking the algorithm?
hard
A. Convert the list to arrays, partition values, then rebuild the list to handle duplicates safely.
B. Use the same in-place pointer rearrangement but skip nodes already processed to avoid infinite loops.
C. Modify the algorithm to clone nodes when moving them to the less-than-x partition to preserve original nodes.
D. Use two separate lists with dummy heads and append clones of nodes to handle reuse.

Solution

  1. Step 1: Understand the reuse constraint

    Nodes can be reused multiple times, so in-place rearrangement that moves nodes breaks because nodes are unique objects.
  2. Step 2: Evaluate modifications

    In-place rearrangement cannot handle duplicates without cloning. Cloning in-place is complex and error-prone. Using arrays to store values and rebuild the list handles duplicates safely and cleanly.
  3. Step 3: Compare cloning approaches

    Cloning nodes in-place or in two lists adds complexity and risks pointer errors. Arrays simplify the problem.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Rebuilding from arrays safely handles duplicates and reuse [OK]
Hint: Rebuild list from arrays to handle node reuse safely [OK]
Common Mistakes:
  • Trying to rearrange nodes in-place with reuse
  • Cloning nodes without updating pointers correctly
  • Assuming pointer moves work with reused nodes
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