Odd Even Linked List — InterviewPrepKit

Solving tips

Group by POSITION parity (1st, 3rd, ... then 2nd, 4th, ...), not node value parity; re-read the problem.
Unzip in place: keep odd and even tails, save even_head, then repeatedly odd.next = even.next; odd = odd.next; even.next = odd.next; even = even.next, and finally odd.next = even_head.
Loop condition must be 'even and even.next' (testing only odd.next breaks on even-length lists); O(n) time, O(1) space.
Terminate the even chain (even_tail.next = None in the two-dummy variant) or you create a cycle/trailing garbage; two dummy heads are an easier-to-reason alternative at the same complexity.

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

class Solution:
    def oddEvenList(self, 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 clock is fine, but the problem explicitly demands O(1) extra space, so the buckets disqualify it.

Approach 2 — In-place unzip (optimal)

Insight: you never need the buckets — 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 the odd tail is stitched to the even head.

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

class Solution:
    def oddEvenList(self, 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)

Insight: the unzip above is compact but the pointer dance is easy to fumble. The tie-complexity alternative uses two dummy heads and appends each visited node to the matching tail — the standard “partition a list stably” template.

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

class Solution:
    def oddEvenList(self, 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.