☕ DSA Java Articles

Topics › Linked List › Medium Problems of LL

Segregate odd and even nodes in Linked List

Medium TUF ID 628 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given the head of a singly linked list. Group all nodes at odd positions (1st, 3rd, 5th, …) together, followed by all nodes at even positions (2nd, 4th, 6th, …). Within each group the original relative order must be preserved. Return the head of the rearranged list.

“Odd” and “even” refer to the 1-based position of a node, not to its value. The expected solution runs in O(n) time with O(1) extra space, which means re-linking the existing nodes rather than copying values.

Constraints: 0 ≤ n ≤ 10^4 nodes, values fit in a 32-bit signed integer.

static class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

Example 1

head = 1 -> 2 -> 3 -> 4 -> 5
answer = 1 -> 3 -> 5 -> 2 -> 4      // positions 1,3,5 then positions 2,4

Example 2

head = 2 -> 1 -> 3 -> 5 -> 6 -> 4 -> 7
answer = 2 -> 3 -> 6 -> 7 -> 1 -> 5 -> 4   // values are irrelevant, positions decide

Example 3

head = 1 -> 2
answer = 1 -> 2                     // already segregated

Approach 1: Brute force, collect values and overwrite

Intuition. Walk the list twice: the first walk hops two nodes at a time starting at position 1 and records those values; the second walk does the same starting at position 2. Concatenating the two value sequences gives the desired order. Then walk the list a third time and write the collected values back into the nodes one by one.

Algorithm.

  1. Start at head and, while the pointer is non-null, append its value and jump two nodes ahead (stop if there is no second node).
  2. Start at head.next (if it exists) and do the same.
  3. Walk from head and copy the collected values back into the nodes in order.
  4. Return head.
static ListNode bruteForce(ListNode head) {
    List<Integer> values = new ArrayList<>();
    ListNode t = head;
    while (t != null) {                          // positions 1, 3, 5, ...
        values.add(t.val);
        t = (t.next == null) ? null : t.next.next;
    }
    t = (head == null) ? null : head.next;
    while (t != null) {                          // positions 2, 4, 6, ...
        values.add(t.val);
        t = (t.next == null) ? null : t.next.next;
    }
    int i = 0;
    for (ListNode cur = head; cur != null; cur = cur.next) cur.val = values.get(i++);
    return head;
}

Complexity. Time O(n): three passes with constant work per node. Space O(n): the list of collected values.

The two-step jump is written as t = (t.next == null) ? null : t.next.next so that a list of odd length (where the last odd-position node has no successor) does not throw a NullPointerException.

This is correct, but it moves values rather than nodes and uses linear extra memory. The intended solution keeps every node object where the caller can still find it and uses only a few pointers.

Approach 2: Optimal, weave two chains

Intuition. Picture the list as two interleaved chains: the odd chain 1 -> 3 -> 5 -> ... and the even chain 2 -> 4 -> 6 -> .... Keep a pointer odd on the end of the odd chain and a pointer even on the end of the even chain. The next odd node is always even.next, and once we attach it, the next even node is odd.next (the node that followed the new odd node). Repeating this unweaves the list in a single pass. At the end, the odd chain’s tail is linked to the saved head of the even chain.

Algorithm.

  1. If the list has fewer than two nodes, return it unchanged.
  2. Set odd = head, even = head.next, and remember evenHead = head.next.
  3. While even and even.next are both non-null:
    • odd.next = even.next; odd = odd.next (attach the next odd node).
    • even.next = odd.next; even = even.next (attach the next even node).
  4. Set odd.next = evenHead and return head.

The loop condition is the key. If even is null, the list had odd length and the odd chain already ends with the last node. If even.next is null, the list had even length and the even chain already ends with the last node. In both cases there is nothing left to re-link, and the final odd.next = evenHead completes the answer.

static ListNode optimal(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode odd = head, even = head.next, evenHead = head.next;
    while (even != null && even.next != null) {
        odd.next = even.next;        // the next odd node sits right after the current even one
        odd = odd.next;
        even.next = odd.next;        // the next even node sits right after the new odd one
        even = even.next;
    }
    odd.next = evenHead;             // odd chain is complete; hang the even chain after it
    return head;
}

Dry run on 1 -> 2 -> 3 -> 4 -> 5:

iteration odd chain even chain odd even
start 1 2 1 2
1 1 -> 3 2 -> 4 3 4
2 1 -> 3 -> 5 2 -> 4 -> null 5 null
finish 1 -> 3 -> 5 -> 2 -> 4      

After iteration 2, even is null so the loop stops; odd.next = evenHead joins the chains.

Complexity. Time O(n): each node is re-linked exactly once. Space O(1): three pointers.

The Java test verifies, for the optimal method, that the result uses exactly the same node objects as the input (same count, and every original node still present), not merely that the values come out in the right order.

Edge cases and pitfalls