Odd Even Linked List

📋

Odd Even Linked List

Edge cases:

</>

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
}

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

Try testing your code on empty and single node lists to handle base cases.

Check your indexing and linking logic carefully to avoid off-by-one and grouping errors.

Optimize your solution to run in linear time with constant extra space.

t1_01basic

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

Expected[1,3,5,2,4]

⏱ Performance - must finish in 2000ms

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

💡 Think about separating nodes by their position parity.

💡 Use two pointers to track odd and even nodes separately.

💡 Link odd nodes together, then append even nodes at the end.

Why it failed: Output order incorrect: likely mixing odd and even nodes or not preserving relative order. Fix by maintaining separate odd and even pointers and linking odd list to even list at the end.

✓ Correctly separates and concatenates odd and even nodes preserving order.

t1_02basic

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

Expected[2,3,7,1,5,4,6]

⏱ Performance - must finish in 2000ms

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

💡 Index nodes starting from 1 to separate odd and even positions.

💡 Track last odd and even nodes to link properly.

💡 After processing all nodes, link last odd node to first even node.

Why it failed: Incorrect output due to not correctly indexing nodes or linking last odd node to even list head. Fix by careful index tracking and final concatenation.

✓ Correctly reorders nodes by odd and even positions.

t2_01edge

Input{"head":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty list input returns empty list.

💡 Check if head is None/null at start.

💡 Return immediately if list is empty.

💡 No processing needed for empty input.

Why it failed: Fails on empty input by not handling null head. Fix by adding initial check for empty list and returning head immediately.

✓ Handles empty list input correctly.

t2_02edge

Input{"head":[10]}

Expected[10]

⏱ Performance - must finish in 2000ms

Single node list returns same list unchanged.

💡 Single node means odd and even lists are the same.

💡 No rearrangement needed if only one node.

💡 Return head as is for single node input.

Why it failed: Fails single node by altering or breaking list. Fix by checking if next node exists before rearranging.

✓ Correctly returns single node list unchanged.

t2_03edge

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

Expected[7,7,7,7]

⏱ Performance - must finish in 2000ms

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

💡 Values may be identical but positions differ.

💡 Separate nodes by position, not value.

💡 Maintain relative order within odd and even groups.

Why it failed: Fails to preserve relative order for identical values. Fix by linking nodes in original order within odd and even groups.

✓ Preserves order correctly even with identical values.

t2_04edge

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

Expected[1,2]

⏱ Performance - must finish in 2000ms

Two node list; odd node followed by even node.

💡 Check behavior with minimal even nodes.

💡 Ensure odd node is first and even node second.

💡 No rearrangement needed beyond linking odd to even.

Why it failed: Fails two node case by swapping or mislinking nodes. Fix by maintaining odd node first and linking even node after.

✓ Correctly handles two node list.

t3_01corner

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

Expected[1,3,5,2,4,6]

⏱ Performance - must finish in 2000ms

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

💡 Check handling when even list length equals odd list length.

💡 Ensure even list tail points to None to avoid cycles.

💡 Link odd tail to even head after processing all nodes.

Why it failed: Fails by creating cycle or incorrect tail pointer in even list. Fix by setting even tail next to None before linking.

✓ Handles even length lists without cycles.

t3_02corner

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

Expected[1,3,5,7,9,2,4,6,8]

⏱ Performance - must finish in 2000ms

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

💡 Verify indexing starts at 1, not 0.

💡 Ensure last odd node links to first even node.

💡 Check no nodes are skipped or duplicated.

Why it failed: Off-by-one error causing wrong node grouping or missing nodes. Fix by correctly indexing nodes starting at 1 and linking properly.

✓ Correctly handles indexing and grouping for odd length lists.

t3_03corner

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

Expected[1,2,1,2,2,1]

⏱ Performance - must finish in 2000ms

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

💡 Group nodes by position parity, not by node value.

💡 Do not reorder nodes by value.

💡 Maintain original relative order within odd and even groups.

Why it failed: Incorrect grouping by node value instead of position parity. Fix by grouping nodes strictly by their index parity.

✓ Correctly groups nodes by position parity regardless of values.

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]}

Expectednull

⏱ Performance - must finish in 2000ms

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

💡 Use a single pass with two pointers to separate odd and even nodes.

💡 Avoid extra space beyond O(1).

💡 Do not use recursive or exponential time approaches.

Why it failed: TLE due to O(n^2) or exponential complexity. Fix by implementing O(n) single pass solution with constant extra space.

✓ Solution runs in O(n) time confirming optimal complexity.

Practice

1. You are given a singly linked list where each node contains an additional pointer that can point to any node in the list or null. The task is to create a deep copy of this list, preserving both the next and random pointer structure. Which approach guarantees an optimal solution with O(n) time and O(1) extra space?

easy

A. Interleave copied nodes within the original list, assign random pointers using the interleaved structure, then separate the lists.

B. Use a hash map to store original-to-copy node mappings and create the copy in two passes.

C. Use a recursive function with memoization to copy nodes and their random pointers.

D. Traverse the list multiple times, copying nodes and random pointers separately without extra data structures.

Solution

1. Step 1: Understand the problem constraints

   The problem requires copying a complex linked list with random pointers efficiently.

2. Step 2: Identify the optimal approach

   Interleaving copied nodes within the original list allows assigning random pointers without extra space, then separating the lists restores the original and creates the copy.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Interleaving nodes achieves O(n) time and O(1) space [OK]

Hint: Interleaving nodes avoids extra space for mapping [OK]

Common Mistakes:

• Assuming recursion is always optimal
• Using extra hash maps increases space complexity
• Trying multiple traversals without mapping fails random pointer assignment

2. What is the time complexity of the recursive approach that converts a binary number in a linked list to an integer by accumulating the value with bit shifts?

medium

A. O(n log n) due to bit shifts at each node

B. O(n^2) because recursion stack causes repeated computations

C. O(n) because each node is visited once with constant work

D. O(n) time but O(n^2) space due to recursion stack

Solution

1. Step 1: Analyze time per node

   Each node is processed once, performing a constant number of bit operations (shift and OR).

2. Step 2: Consider recursion overhead

   Recursion depth is n, but no repeated computations occur; each call does O(1) work.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear traversal with constant work per node [OK]

Hint: Bit shifts are O(1) operations, not O(log n) [OK]

Common Mistakes:

• Assuming bit shifts cost O(log n)
• Confusing recursion stack space with time complexity
• Thinking recursion causes repeated work

3. What is the space complexity of the optimal approach that copies a linked list with random pointers by weaving copied nodes into the original list and then separating them?

medium

A. O(n) due to storing copied nodes in a hash map

B. O(n) because each node's random pointer requires extra space

C. O(n) due to recursion stack in the copying process

D. O(1) because no extra data structures are used besides new nodes

Solution

1. Step 1: Identify auxiliary space usage

   The optimal approach weaves copied nodes directly into the original list without using extra hash maps or recursion.

2. Step 2: Confirm space complexity

   Only new nodes are created, which is required output space, so auxiliary space is O(1).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   No extra data structures or recursion stack used [OK]

Hint: Weaving nodes avoids extra mapping space [OK]

Common Mistakes:

• Confusing output space with auxiliary space
• Assuming recursion is used and adds stack space
• Thinking random pointers require extra space

4. The following code attempts to reorder a linked list using the recursive approach. Identify the line containing the subtle bug that can cause infinite loops or cycles when traversing the reordered list.

def reorderList(head):
    def helper(front, back):
        if not back:
            return True
        if not helper(front, back.next):
            return False
        if front[0] == back or front[0].next == back:
            # Missing termination here
            return False
        tmp = front[0].next
        front[0].next = back
        back.next = tmp
        front[0] = tmp
        return True
    helper([head], head)

medium

A. Line with 'if not back: return True' -- base case incorrect

B. Line with 'if front[0] == back or front[0].next == back:' -- missing back.next = None

C. Line with 'front[0].next = back' -- incorrect pointer assignment

D. Line with 'front[0] = tmp' -- front pointer update is wrong

Solution

1. Step 1: Identify termination condition

   The condition checking if front meets back must terminate the list by setting back.next = None.

2. Step 2: Locate missing termination

   Line with 'if front[0] == back or front[0].next == back:' lacks 'back.next = None', causing cycles.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing null termination leads to infinite traversal [OK]

Hint: Termination must set back.next = None to avoid cycles [OK]

Common Mistakes:

• Forgetting to null-terminate reordered list
• Misplacing pointer updates
• Incorrect base case handling

5. Suppose the problem is modified so that nodes can be reused multiple times (i.e., after reversing a group, nodes can appear again in subsequent groups). Which of the following changes to the algorithm correctly handles this scenario?

hard

A. Modify the algorithm to create new nodes for each group reversal to avoid modifying original nodes in place.

B. This problem cannot be solved by reversal; instead, use a queue to simulate repeated node usage.

C. Use recursion with memoization to store reversed groups and reuse them without modifying the original list.

D. Use the same iterative reversal approach but reset pointers to allow reusing nodes in multiple groups.

Solution

1. Step 1: Understand node reuse implication

   Reusing nodes means original nodes must remain unchanged or duplicated to appear multiple times.

2. Step 2: Evaluate algorithm modifications

   In-place reversal modifies nodes destructively, so creating new nodes for each group is necessary to preserve original nodes.

3. Step 3: Assess other options

   Resetting pointers (A) breaks list integrity; recursion with memoization (C) is complex and not standard; queue simulation (B) does not solve reversal reuse.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Duplicating nodes preserves original list for reuse [OK]

Hint: Node reuse requires duplication, not in-place reversal [OK]

Common Mistakes:

• Trying to reuse nodes in place
• Ignoring list integrity
• Assuming recursion memoization solves reuse