Segregate even and odd nodes in a Linked List

The problem, simply

You get a linked list of whole numbers. Rearrange it so that all boxes with even numbers come first and all boxes with odd numbers come after them.

Inside each group, keep the old order. If 8 came before 2 in the input, 8 must still come before 2. Give back the new head.

A story to remember it

Picture it

Examples

Way 1: the simple way

Copy the numbers out, then write them back in the right order.

1. Walk the chain. Put even numbers in one list and odd numbers in another.
2. Walk the chain again and write all the even numbers into the boxes, then all the odd numbers.

import java.util.*;

class Solution {
    public Node divide(Node head) {
        List<Integer> evens = new ArrayList<>(), odds = new ArrayList<>();
        for (Node cur = head; cur != null; cur = cur.next) {
            if (cur.data % 2 == 0) evens.add(cur.data);
            else odds.add(cur.data);
        }
        Node cur = head;
        for (int x : evens) { cur.data = x; cur = cur.next; }   // evens first
        for (int x : odds) { cur.data = x; cur = cur.next; }    // then odds
        return head;
    }
}

How long it takes: two walks, O(n). Extra room: the two lists hold every number, O(n). It also copies numbers instead of moving boxes, which many interviewers do not accept.

Way 2: the clever way

Do what the teacher did. Build two lines out of the real boxes, then join them.

1. Make two dummy boxes, one for the even line and one for the odd line. Each line has a tail finger.
2. Walk the chain. Hook each box to the end of its line and move that line's tail.
3. Hook the end of the even line to the first box of the odd line.
4. Set the odd tail's next to null, because it may still point to an old neighbor.
5. Give back the box after the even dummy.

class Solution {
    public Node divide(Node head) {
        Node evenDummy = new Node(0), oddDummy = new Node(0);
        Node evenTail = evenDummy, oddTail = oddDummy;
        for (Node cur = head; cur != null; cur = cur.next) {
            if (cur.data % 2 == 0) { evenTail.next = cur; evenTail = cur; }
            else { oddTail.next = cur; oddTail = cur; }
        }
        evenTail.next = oddDummy.next;   // evens, then odds
        oddTail.next = null;             // cut the old arrow at the end
        return evenDummy.next;           // works even when there are no evens
    }
}

How long it takes: one walk, O(n). Extra room: two dummy boxes and two tails, O(1). Boxes are moved, not copied, and the order inside each group is kept, so this split is stable.

Watch out for

• Testing odd with x % 2 == 1 fails for negative numbers in Java, because -3 % 2 is -1. Test even with x % 2 == 0 instead.
• No even boxes at all: evenTail is still the dummy, so evenDummy.next = oddDummy.next and the answer is the odd line. The code handles it without a special case.
• Return evenDummy.next, not head. The head changes whenever the first box is odd.

What interviewers ask next

• Group by position instead of value (LeetCode 328, odd even linked list): boxes 1, 3, 5 first, then 2, 4, 6. Use two fingers that jump two boxes each: odd.next = even.next, even.next = odd.next, then join.
• Odds first, then evens? Swap which line is joined to which.
• Split by a value x instead of parity (LeetCode 86, partition list): boxes smaller than x first, others after. Same two lines.
• Three groups, like 0s, 1s and 2s? Three lines, joined in order. That is the "sort a list of 0s, 1s and 2s" problem.

Remember this

Grown-up words: the boxes are nodes, the two lines are two sublists built with dummy head nodes, the tails are tail pointers, and keeping the old order inside each group makes this a stable partition.