A live auction tape is a singly linked list of bids in arrival order. Product wants the odd slots — first bid, third, fifth — as the featured reel, then the even slots as the remainder, same relative order inside each reel. The intern version kept every bid whose amount was odd. Even-dollar openers vanished. Odd-dollar seconds jumped the queue. The tape still had the right numbers somewhere. The positions were gone.

Odd-even grouping on a singly linked list means odd next positions, then even positions — not odd values. Positions are 1-indexed from head. The linked list post owns splice, dummy nodes, and why get(i) walks. Reverse and merge already taught that copying values is not a rewire of the nodes you were given. Here we only care about two tails and one join.

The problem

Given the head of a singly linked list, group every odd-positioned node, then every even-positioned node, and return the new head. Relative order inside the odd group and inside the even group stays as it was. Prefer one pass and O(1) extra space. Empty and single-node lists are already grouped.

1 → 2 → 3 → 4 → 5 → null           →  1 → 3 → 5 → 2 → 4 → null
1 → 2 → 3 → 4 → null               →  1 → 3 → 2 → 4 → null
2 → 1 → 3 → 5 → 6 → 4 → 7 → null   →  2 → 3 → 6 → 7 → 1 → 5 → 4 → null

The third trace is the trap: 2 stays first because it sits at position 1, not because it is even. 1 moves with the even positions.

A node is the usual two fields:

final class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

Note: In-place means the same node objects, new next links. Head does not move: position 1 is always odd, so the returned head is the original head.

Two ArrayLists of nodes is the honest extra-space brute

Walk once. Drop odd-positioned nodes into one list, even-positioned into another. Then rewire next along odds, hang evens off the last odd, and null-terminate the last even. The objects are the ones you were handed. The extra arrays are not O(1).

ListNode oddEvenByLists(ListNode head) {
    if (head == null) {
        return null;
    }
    List<ListNode> odds = new ArrayList<>();
    List<ListNode> evens = new ArrayList<>();
    boolean oddSlot = true;
    for (ListNode n = head; n != null; n = n.next) {
        if (oddSlot) {
            odds.add(n);
        } else {
            evens.add(n);
        }
        oddSlot = !oddSlot;
    }
    for (int i = 0; i < odds.size() - 1; i++) {
        odds.get(i).next = odds.get(i + 1);
    }
    odds.get(odds.size() - 1).next = evens.isEmpty() ? null : evens.get(0);
    for (int i = 0; i < evens.size() - 1; i++) {
        evens.get(i).next = evens.get(i + 1);
    }
    if (!evens.isEmpty()) {
        evens.get(evens.size() - 1).next = null;
    }
    return odds.get(0);
}

Collect before you rewire. The for walk still uses the original next. At a handful of bids this is a rounding error. In production you paid O(n) extra references for a splice you can do with two fingers.

Two tails, save evenHead, join once

You already hold the first odd node (head) and the first even node (head.next). Keep odd on the tail of the odd chain and even on the tail of the even chain. Save evenHead before the walk so the join does not search.

Each step peels the next odd onto the odd tail, then the next even onto the even tail. The loop guard is even != null && even.next != null: if there is no remaining odd after this even, the chains are already complete.

Walk 1 → 2 → 3 → 4 → 5:

start: odd=1  even=2  evenHead=2

step 1: 1.next = 3, odd=3
        2.next = 4, even=4
        odd chain  1 → 3 → 4 → 5
        even chain 2 → 4 → 5

step 2: 3.next = 5, odd=5
        4.next = null, even=null
        odd chain  1 → 3 → 5
        even chain 2 → 4 → null

join: 5.next = evenHead
      1 → 3 → 5 → 2 → 4 → null

No dummy. The first splice already has a predecessor: odd starts as head. Merge needed a dummy because the first survivor might come from either list. Here position 1 is never in doubt.

ListNode oddEvenList(ListNode head) {
    if (head == null) {
        return null;
    }
    ListNode odd = head;
    ListNode even = head.next;
    ListNode evenHead = even;
    while (even != null && even.next != null) {
        odd.next = even.next;
        odd = odd.next;
        even.next = odd.next;
        even = even.next;
    }
    odd.next = evenHead;
    return head;
}

Time is O(n) — each node is visited once. Space is O(1) besides the three pointers.

Empty list: the null check returns null. One node: even is null, the loop never runs, odd.next is already null, you return that node. Two nodes: even.next is null, the loop never runs, odd.next is already evenHead.

Forgetting odd.next = evenHead leaves two chains and a featured reel that never meets the remainder. The last even must point at null — the loop writes that when it assigns even.next = odd.next on the final odd. Skip that write and even still points into the old suffix, which is now the odd chain: a cycle.

What interviewers usually poke next

  • Odd values, not odd positions. val % 2 is a partition by payload. This prompt is a partition by index. Say the difference before you write a loop. A list of even values still has an odd first slot.
  • Even group first. Same two tails; join evenTail.next = oddHead and return evenHead. Head does move.
  • 0-indexed positions. Then head is even. The prompt here is 1-indexed; ask if they switch.
  • Dummy heads for both groups. Legal bookkeeping, extra nodes, not needed. You already have both first nodes.
  • Do it with the ArrayLists. Correct identity, O(n) extra space. Say why two tails are the bill they asked for.

You are done with this problem when you can regroup 1 → 2 → 3 → 4 → 5 on a whiteboard without a cycle, and you can refuse val % 2 out loud before the first splice.