Odd Even Linked List

Group the nodes at odd positions first, then the nodes at even positions, by threading two chains through the list and joining them at the end.

The idea

Positions alternate odd, even, odd, even. Keep two tails: odd at the end of the odd chain and even at the end of the even chain. The node after even is always the next odd one, so hang it on odd; the node after that is the next even one, so hang it on even. When the list runs out, point the last odd node at evenHead, the first even node you saved at the start.

Code

public ListNode OddEvenList(ListNode head) {
    if (head == null) return null;
    ListNode odd = head, even = head.next, evenHead = even;
    while (even != null && even.next != null) {
        odd.next = even.next; // skip over the even node
        odd = odd.next;
        even.next = odd.next; // skip over the new odd node
        even = even.next;
    }
    odd.next = evenHead; // odd chain, then the even chain
    return head;
}

Tips

• Positions are 1-indexed and it is the position that counts, not the value: in 2, 1, 3, 5 the odd positions hold 2 and 3.
• Save evenHead before the loop. By the end nothing else points at the first even node.
• The loop checks even and even.next, because those are the two nodes each round needs. With an even count the loop ends on even == null, with an odd count on even.next == null.

In the .NET library

The rewiring changes only next references; no ListNode is created, so the extra space is O(1).