Odd Even Linked List

Given the head of a singly linked list, number its nodes by position starting from 1 (the head is position 1, an odd position). Rearrange the list so that all nodes at odd positions come first, followed by all nodes at even positions, and return the new head.

Within each group, the nodes must keep the relative order they had in the original list. Note that the grouping is by position, not by whether the values are odd or even.

Aim for O(1) extra space and O(n) time. The list is shown as an array of its values from head to tail.

Example 1

Example 2

Example 3

Constraints

• The number of nodes is in the range [0, 104]
• -106 <= Node.val <= 106

Pattern Path · Linked Lists · problem 73 of 169

Start simple

Copy the values into two arrays (odd and even positions) and write them back or build a new list: O(n) time but O(n) extra space.

The key idea

The odd-position nodes and even-position nodes already alternate, so you can unzip the list into two chains in place and then join them.

Let odd = head and even = head.next, and save evenHead = even. While even and even.next exist: the next odd node is even.next, so set odd.next = even.next and advance odd; the next even node is now odd.next, so set even.next = odd.next and advance even. Each pointer jumps over one node of the other group, which is exactly how the two chains separate while keeping their original order.

The loop ends when the even chain runs out (even length) or has one node left with nothing after it (odd length). In both cases odd is on the last odd node, so odd.next = evenHead stitches the groups together. Only a constant number of pointers is used.

Complexity

• Time: O(n)
• Space: O(1)

Python

class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None
        odd, even = head, head.next
        even_head = even
        while even and even.next:
            odd.next = even.next   # next odd node
            odd = odd.next
            even.next = odd.next   # next even node
            even = even.next
        odd.next = even_head       # odd chain, then even chain
        return head

JavaScript

var oddEvenList = function(head) {
  if (!head) return null;
  let odd = head, even = head.next;
  const evenHead = even;
  while (even && even.next) {
    odd.next = even.next; // next odd node
    odd = odd.next;
    even.next = odd.next; // next even node
    even = even.next;
  }
  odd.next = evenHead;    // odd chain, then even chain
  return head;
};

What the interviewer is checking

The interviewer wants clean in-place pointer manipulation: splitting a list into two interleaved chains and reconnecting them without losing nodes.

Mistakes to avoid

• Grouping by the node values instead of their positions.
• Forgetting to save the head of the even chain before rewiring.
• A wrong loop condition that dereferences null on odd or even lengths, or empty input.

Follow-ups to expect

• Split into k groups by position mod k. (k tails, then chain them.)
• Group by value parity instead, stable. (Same unzip, test values.)
• Undo it: interleave the two halves back. (Zip two pointers alternately.)

In real software

Splitting a stream into alternating halves is used to de-interleave stereo audio channels and to partition work between two consumers, and the in-place relinking keeps it allocation-free.

Practice next