Odd-Even Linked List

Medium15–20 min

Topics

Linked ListReversal

Companies

AmazonMicrosoftFacebook

Given the head of a singly linked list, regroup its nodes so every node that started at an odd position (1st, 3rd, 5th, …) comes before every node that started at an even position (2nd, 4th, 6th, …) — each group keeping its own original relative order — and return the new head. The regrouping happens in place; no node's value changes, only the links between them. Two pointers walking the list together can build both groups in a single pass: one pointer always skips ahead to the next odd-positioned node, the other always skips ahead to the next even-positioned node, and each skip permanently splices that node into its group's chain. Once the even pointer runs out of nodes, every node has landed in exactly one of the two chains, and pointing the odd chain's tail at the remembered start of the even chain joins them into the final list.

Test Case 1:

Input:head = [4, 8, 1, 6, 3]

Output:[4, 1, 3, 8, 6]

Explanation:Odd-positioned nodes (1st, 3rd, 5th) come first in their original order, then even-positioned nodes (2nd, 4th) follow in their original order.

Test Case 2:

Input:head = [9, 2]

Output:[9, 2]

Explanation:With only 2 nodes, one odd-positioned and one even-positioned, the order is already correct.

Test Case 3:

Input:head = [5]

Output:[5]

Explanation:A single node is always odd-positioned — nothing to regroup.

Constraints

◆0 ≤ number of nodes in head ≤ 200
◆-1000 ≤ node value ≤ 1000
◆Positions are counted from 1 — the first node is odd-positioned

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Collect into Two Lists, Then Write Back

Good

Walk the list once, sorting every value into one of two arrays based on whether its position is odd or even. Concatenate the odd-positioned values before the even-positioned ones, then walk the list a second time, overwriting each node's value in that new order. Correct, but the two arrays cost O(n) extra space where the optimal solution needs none.

TimeO(n)

SpaceO(n)

Java

Try it out

// Node definition used in this problem:
// class Node {
//     int val;
//     Node next;
// }

class Solution {
    public Node oddEvenList(Node head) {
        List<Integer> odds = new ArrayList<>();
        List<Integer> evens = new ArrayList<>();
        Node curr = head;
        int idx = 0;
        while (curr != null) {
            if (idx % 2 == 0) {
                odds.add(curr.val);
            } else {
                evens.add(curr.val);
            }
            curr = curr.next;
            idx++;
        }
        List<Integer> combined = new ArrayList<>(odds);
        combined.addAll(evens);
        curr = head;
        for (int v : combined) {
            curr.val = v;
            curr = curr.next;
        }
        return head;
    }
}

Optimal — Relink in Place with Two Pointers

Optimal

Carry two pointers, odd and even, starting at the first and second nodes, and remember the even list's head separately since it needs to be reattached at the very end. At each step, odd skips over the node right after it (landing on the next odd-positioned node), and even does the same (landing on the next even-positioned node) — splicing every node out of its original spot and into one of the two growing chains as the pointers advance together. Once even runs out of nodes, the odd chain's tail is pointed at the remembered even-chain head, joining the two chains with no extra memory beyond the pointers themselves.