#328 Odd Even Linked List

frequently reported atAmazon Microsoft

the problem

In plain words

Rearrange a singly linked list so that the nodes at odd positions (1st, 3rd, 5th, …) come first and the nodes at even positions follow, each group keeping its original order. Positions matter, not values. Use O(1) extra space and O(n) time.

in head = [1,2,3,4,5]

out [1,3,5,2,4]

in head = [2,1,3,5,6,4,7]

out [2,3,6,7,1,5,4]

Positions 1, 3, 5, 7 hold 2, 3, 6, 7; positions 2, 4, 6 hold 1, 5, 4.

0 ≤ number of nodes ≤ 10⁴
-10⁶ ≤ Node.val ≤ 10⁶

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternIn-place linked-list rewiring

Unzip the list into two chains as you walk — odd and even take turns grabbing the next node — then glue the odd chain's tail to the saved head of the even chain.

solutions

From brute force to optimal

Sort nodes into two lists by position, then relink them: odd list first, even list after.

Walk the list, adding each node to odd or even by position.
Append the even list to the odd list.
Relink every next; the last node gets null.

timeO(n)

One pass to sort, one to relink.

spaceO(n)

Two lists of node references — breaks the O(1)-space rule.

javajava.util.*

1class Solution {2    public ListNode oddEvenList(ListNode head) {3        List<ListNode> odd = new ArrayList<>(), even = new ArrayList<>();4        int position = 1;5        for (ListNode p = head; p != null; p = p.next, position++) {6            (position % 2 == 1 ? odd : even).add(p);     // sort nodes by position, not by value7        }8        odd.addAll(even);                                // odd positions first, order kept9        for (int i = 0; i + 1 < odd.size(); i++) odd.get(i).next = odd.get(i + 1);10        if (!odd.isEmpty()) odd.get(odd.size() - 1).next = null;11        return odd.isEmpty() ? null : odd.get(0);12    }13}

odd starts at head, even at head.next. Each step, odd jumps over one even node and even jumps over one odd node. Finally odd.next = evenHead.

odd = head, even = head.next, 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.

timeO(n)

Each node is visited once.

spaceO(1)

Three references.

javajava.util.*

1class Solution {2    public ListNode oddEvenList(ListNode head) {3        if (head == null) return null;4        ListNode odd = head, even = head.next, evenHead = even; // remember where the even chain starts5        while (even != null && even.next != null) {6            odd.next = even.next;  // odd skips over one even node7            odd = odd.next;8            even.next = odd.next;  // even skips over one odd node9            even = even.next;10        }11        odd.next = evenHead;       // glue: last odd node → first even node12        return head;13    }14}

in the room

How to say it in the interview

talk track

Clarify: positions, not values — the second example puts odd values at even positions.
Save evenHead before the loop: after unzipping, nothing else points to it.
Explain the loop condition even != null && even.next != null: it handles odd and even lengths without extra checks.

traps

Grouping by value parity instead of position.
Losing the even chain's head — save evenHead first.

what they ask next

Follow-ups

Split into k chains by position (i % k)?

Keep k dummy heads and k tails in arrays; append node i to chain i % k; then join the chains in order and end the last one with null.

before you submit

Edge cases to test

Empty list or one node → return it as is.
Two nodes → unchanged.
Even length: the even chain ends with null on its own.
All values even — positions still decide the groups.

practise next