Odd Even Linked List — InterviewPrepKit

Problem

Given the head of a singly linked list, regroup its nodes so that all nodes in odd positions (1st, 3rd, 5th, …, counting from 1) come first, followed by all nodes in even positions (2nd, 4th, 6th, …). Within each group the original relative order must be preserved.

Note the grouping is by position in the list, not by whether the node’s value is odd or even.

You must do it in O(1) extra space and O(n) time.

Examples

Input: head = [1, 2, 3, 4, 5] → Output: [1, 3, 5, 2, 4] Odd positions hold 1, 3, 5; even positions hold 2, 4.
Input: head = [2, 1, 3, 5, 6, 4, 7] → Output: [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.
Input: head = [7] → Output: [7] A single node is trivially already grouped.

Constraints

0 <= n <= 10^4 where n is the number of nodes.
-10^6 <= Node.val <= 10^6.
Required: O(1) extra space, O(n) time — so no copying nodes into an array in the intended solution.

Think about it first

Hint 1

If space were free, you could walk the list once collecting odd-position nodes in one bucket and even-position nodes in another, then chain the buckets. What would the in-place version of "two buckets" look like?

Hint 2

Keep two tails growing in place: an odd tail and an even tail. Each node you visit belongs to exactly one of them, and the nodes alternate.

Hint 3

Let `odd` start at node 1 and `even` at node 2 (save node 2 as `even_head`). Repeatedly do `odd.next = even.next; odd = odd.next; even.next = odd.next; even = even.next` — you are unzipping the list into two chains. Finish by pointing the odd tail at `even_head`.

TL;DR

Unzip the list into an odd chain and an even chain in one pass, then splice — O(n) time, O(1) space.

Approach 1 — Brute force: two buckets of nodes

Walk the list once, appending each node to an odd bucket or an even bucket by position, then rebuild by chaining the buckets.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

def oddEvenList(head: Optional[ListNode]) -> Optional[ListNode]:
    odds: List[ListNode] = []
    evens: List[ListNode] = []
    node, pos = head, 1
    while node:
        (odds if pos % 2 == 1 else evens).append(node)
        node = node.next
        pos += 1
    ordered = odds + evens
    for i in range(len(ordered) - 1):
        ordered[i].next = ordered[i + 1]
    if ordered:
        ordered[-1].next = None
    return head

Time O(n), space O(n). The time is fine, but the problem requires O(1) extra space, so the buckets disqualify this approach.

Approach 2 — In-place unzip (optimal)

The buckets are unnecessary: the two groups can grow in place. Keep an odd tail and an even tail. The next odd node is always even.next, and the next even node is always odd.next after odd advances. This unzips the alternating list into two chains in a single pass, then stitches the odd tail to the even head.

flowchart LR
    subgraph Input
      A1[1] --> A2[2] --> A3[3] --> A4[4] --> A5[5]
    end
    subgraph Result
      O1[1] --> O3[3] --> O5[5] --> E2[2] --> E4[4]
    end

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

def oddEvenList(head: Optional[ListNode]) -> Optional[ListNode]:
    if not head or not head.next:
        return head
    odd = head
    even_head = head.next
    even = even_head
    while even and even.next:
        odd.next = even.next   # next odd node
        odd = odd.next
        even.next = odd.next   # next even node (may be None)
        even = even.next
    odd.next = even_head
    return head

Walkthrough on [1, 2, 3, 4, 5] (even_head = node 2):

step	action	odd chain	even chain
start	odd=1, even=2	1	2
1	odd.next=3; even.next=4	1→3	2→4
2	odd.next=5; even.next=None	1→3→5	2→4
end	loop exits (even.next is None); odd.next=even_head	1→3→5→2→4	—

Output: [1, 3, 5, 2, 4].

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

Approach 3 — Two dummy heads (same complexity, easier to reason about)

The unzip above is compact but its pointer updates are easy to get wrong. This alternative has the same complexity and uses two dummy heads, appending each visited node to the matching tail — the standard template for stably partitioning a list.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

def oddEvenList(head: Optional[ListNode]) -> Optional[ListNode]:
    odd_dummy, even_dummy = ListNode(), ListNode()
    odd_tail, even_tail = odd_dummy, even_dummy
    node, pos = head, 1
    while node:
        if pos % 2 == 1:
            odd_tail.next = node
            odd_tail = node
        else:
            even_tail.next = node
            even_tail = node
        node = node.next
        pos += 1
    even_tail.next = None
    odd_tail.next = even_dummy.next
    return odd_dummy.next

Walkthrough on [2, 1, 3, 5, 6, 4, 7]: positions 1..7 route 2,3,6,7 to the odd tail and 1,5,4 to the even tail, giving 2→3→6→7 and 1→5→4; stitching yields [2, 3, 6, 7, 1, 5, 4].

Time O(n), space O(1) — the two dummies are constants, not per-node storage.

Common pitfalls

Grouping by node value parity instead of position parity — read the problem twice.
Forgetting even_tail.next = None (or relying on the unzip loop’s last write): a dangling next pointer creates a cycle or trailing garbage.
Losing even_head: once odd starts skipping over even nodes, the only handle on the even chain’s start is the saved pointer.
In the unzip version, the loop condition must be even and even.next; testing only odd.next breaks on even-length lists.

Pattern takeaway

Stable in-place partitioning of a linked list — by position parity here, by value threshold in Partition List — is always the same shape: grow two tails, terminate both chains, splice once at the end. Dummy heads cost nothing and remove every special case at the front of a chain.