Q&A

How to segregate even and odd numbers in a linked list

By AlgoInsight Team2026-06-07data-structures

Overview

Given a singly linked list, reorder it so even numbers precede odd numbers. The clean technique maintains two chains as you traverse once: append each node to either the "even" chain or the "odd" chain based on its value, then join them. Reusing the existing nodes (not creating new ones) keeps it O(1) extra space.

graph LR
    A[Traverse original list] --> B{node value even?}
    B -->|even| C[append to EVEN list]
    B -->|odd| D[append to ODD list]
    C & D --> E[End: even.tail.next = odd.head]
    E --> F[Result: evens... then odds...]
    style E fill:#1e1b4b,color:#fff

The Two-List Approach

Use four pointers: heads and tails of an even list and an odd list. Walk the original list; relink each node onto the appropriate tail.

class Node {
    int val;
    Node next;
    Node(int val) { this.val = val; }
}

public Node segregateEvenOdd(Node head) {
    Node evenHead = null, evenTail = null;   // even sub-list
    Node oddHead = null, oddTail = null;     // odd sub-list

    Node curr = head;
    while (curr != null) {
        if (curr.val % 2 == 0) {             // even
            if (evenHead == null) evenHead = evenTail = curr;
            else { evenTail.next = curr; evenTail = curr; }
        } else {                              // odd
            if (oddHead == null) oddHead = oddTail = curr;
            else { oddTail.next = curr; oddTail = curr; }
        }
        curr = curr.next;
    }

    if (evenHead == null) return oddHead;     // no evens
    evenTail.next = oddHead;                   // link evens → odds
    if (oddTail != null) oddTail.next = null;  // terminate the list
    return evenHead;
}

Walkthrough

Input:  17 → 15 → 8 → 12 → 10 → 5 → 4 → 1 → 7 → 6
Evens collected: 8 → 12 → 10 → 4 → 6
Odds collected:  17 → 15 → 5 → 1 → 7
Linked:          8 → 12 → 10 → 4 → 6 → 17 → 15 → 5 → 1 → 7

Note the relative order within each group is preserved (stable).

Python Version

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

def segregate_even_odd(head):
    even_head = even_tail = None
    odd_head = odd_tail = None
    curr = head
    while curr:
        nxt = curr.next
        curr.next = None                      # detach
        if curr.val % 2 == 0:
            if not even_head: even_head = even_tail = curr
            else: even_tail.next = curr; even_tail = curr
        else:
            if not odd_head: odd_head = odd_tail = curr
            else: odd_tail.next = curr; odd_tail = curr
        curr = nxt
    if not even_head:
        return odd_head
    even_tail.next = odd_head
    return even_head

Critical Details

1. Terminate the final list - set the last odd node's next to null, or you may leave a dangling link or create a cycle.
2. Handle all-even or all-odd lists - if one group is empty, return the other head.
3. Preserve order - appending to tails (not prepending) keeps the original relative order, which is usually expected.
4. Reuse nodes - relink existing nodes rather than allocating new ones, for O(1) extra space.

Complexity

• Time: O(n) - one pass.
• Space: O(1) - only a few pointers; nodes are rearranged in place.

Variations

• "Odds before evens" - swap which list you link first.
• "Segregate by a key/predicate" - generalize the % 2 == 0 test.
• Even/odd by position (LeetCode 328 "Odd Even Linked List") is a different problem - it groups by node index, not value; clarify which is meant.

Why This Matters in Interviews

This tests linked-list pointer manipulation. Interviewers look for the single-pass two-list construction (O(n)/O(1)), correct handling of edge cases (empty groups, terminating the tail to avoid cycles), preserving relative order, and reusing nodes instead of copying. Clarifying "by value vs by position" up front shows good requirement-gathering instincts.

Common Pitfalls

• Forgetting to null-terminate the last node → cycle or dangling pointer.
• Not handling all-even / all-odd inputs (one list stays empty).
• Prepending instead of appending, accidentally reversing within a group.
• Confusing it with the index-based "odd-even linked list" problem.

References

• Linked list (data structure): https://en.wikipedia.org/wiki/Linked_list
• LeetCode 328 "Odd Even Linked List" (index-based variant): https://leetcode.com/problems/odd-even-linked-list/

More answers