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.