Odd Even Linked List

Overview

Odd even linked list means rearranging the list so that all nodes at odd indices (1-based: first node is index 1) come first, followed by all nodes at even indices. Alternatively the problem may use 0-based indices (odd positions = 1st, 3rd, … and even = 2nd, 4th, …). Either way, you do one pass with two Dummy Head lists: one for odd-position nodes and one for even-position nodes. Then connect odd tail to even head and even tail to null. O(n) time, O(1) space.

Key idea: You don't need to count indices; alternate: first node goes to odd list, second to even, third to odd, and so on. Two pointers (oddTail, evenTail) and one pass.

When to Use

• Group nodes by position — Odd positions then even (or vice versa).
• Alternate grouping — Same pattern for any two-way split by position.

How It Works

1. Dummies: oddDummy, evenDummy; oddTail = oddDummy, evenTail = evenDummy.
2. Traverse: Start at head (index 1 or 0). For each node, attach to odd or even list alternately (e.g. odd, even, odd, even …). Advance the corresponding tail.
3. Connect: oddTail.next = evenDummy.next; evenTail.next = null.
4. Return oddDummy.next.

Example 1: Odd Even Linked List (1-based indices)

Problem: Given the head of a singly linked list, group all nodes with odd indices together followed by nodes with even indices. The first node is index 1, second is index 2, etc. Preserve order within each group.

function oddEvenList(head: ListNode | null): ListNode | null {
  if (head === null || head.next === null) return head;
  const oddDummy = new ListNode(-1);
  const evenDummy = new ListNode(-1);
  let oddTail = oddDummy;
  let evenTail = evenDummy;
  let isOdd = true;
  let curr: ListNode | null = head;
  while (curr !== null) {
    const next = curr.next;
    curr.next = null;
    if (isOdd) {
      oddTail.next = curr;
      oddTail = curr;
    } else {
      evenTail.next = curr;
      evenTail = curr;
    }
    isOdd = !isOdd;
    curr = next;
  }
  oddTail.next = evenDummy.next;
  evenTail.next = null;
  return oddDummy.next;
}

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

Example 2: In-Place (No New Nodes, Rewire Only)

Variant: Use only pointer rewiring; don't create dummy nodes (or use existing nodes as "dummy" by keeping oddHead = head, evenHead = head.next).

function oddEvenList(head: ListNode | null): ListNode | null {
  if (head === null || head.next === null) return head;
  let odd = head;
  let even = head.next;
  const 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;
}

• Odd list: head, head.next.next, …; even list: head.next, head.next.next.next, …; then odd.next = evenHead.

Edge Cases

• Empty list — Return null.
• Single node — Only odd; even list empty; oddTail.next = evenDummy.next is null; correct.
• Two nodes — Odd: first; even: second; connect and return.

Common Mistakes

1. Breaking links — When appending to a list, set curr.next = null (or in the in-place version, only update the next pointers that define the two chains) so you don't create cycles.
2. Even tail.next — Set evenTail.next = null so the last even node doesn't point back into the list.
3. Index convention — Confirm whether problem uses 1-based (first = odd) or 0-based (first = even); adjust isOdd initial value or which list gets the first node.

Time and Space Complexity

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

Summary

• Odd even list: Two dummies (odd, even), one pass appending alternately; oddTail.next = evenHead, evenTail.next = null; return oddDummy.next. Or do it in-place with two running pointers.
• See Dummy Head and Partition List for the two-list pattern.