Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Odd Even Linked List

Problem (restated)

Given the head of a singly linked list, group nodes at odd positions first, then even positions (1-based), keeping relative order inside each group. Return the reordered list. Must be O(n) time and O(1) extra space.

Intuition

This is a partition by index, not by value. Keep a tail for the odd chain and a tail for the even chain, walk once, then attach the even chain after the last odd node. Null the last even next or you create a cycle.

Approaches

In-place odd/even pointers

Unverified

Time O(n)Space O(1)

Idea. odd = head, even = head.next, remember evenHead. While even has a next: pull the next odd onto odd.next and the next even onto even.next. Finally odd.next = evenHead.

Walkthrough. 1→2→3→4→5. After the loop: odd chain 1→3→5, even chain 2→4. Stitch: 1→3→5→2→4.

Trade-offs. Canonical interview answer. No dummy nodes; empty and single-node lists fall out naturally. Easy to forget odd.next = evenHead.

Solution

export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

export function oddEvenList(head: ListNode | null): ListNode | null {
  if (!head) return null;
  let odd = head;
  let even = head.next;
  const evenHead = even;
  while (even && even.next) {
    odd.next = even.next;
    odd = odd.next;
    even.next = odd.next;
    even = even.next;
  }
  odd.next = evenHead;
  return head;
}

export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

export function oddEvenList(head: ListNode | null): ListNode | null {
  if (!head) return null;
  let odd = head;
  let even = head.next;
  const evenHead = even;
  while (even && even.next) {
    odd.next = even.next;
    odd = odd.next;
    even.next = odd.next;
    even = even.next;
  }
  odd.next = evenHead;
  return head;
}

Two dummy tails

Unverified

Time O(n)Space O(1)

Idea. Two sentinels. Walk with an index; append to the odd tail or even tail. even.next = null, then odd.next = evenDummy.next. Return oddDummy.next.

Walkthrough. Same list, same result. The sentinels make “first odd / first even” identical to later appends.

Trade-offs. Matches the partition template more literally and is harder to get wrong. One extra pair of dummy nodes (still O(1)). Prefer this if you already think in “two tails, join at the end.”

Solution

export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

export function oddEvenList(head: ListNode | null): ListNode | null {
  const oddDummy = new ListNode(0);
  const evenDummy = new ListNode(0);
  let odd = oddDummy;
  let even = evenDummy;
  let cur = head;
  let i = 1;
  while (cur) {
    if (i % 2 === 1) {
      odd.next = cur;
      odd = odd.next;
    } else {
      even.next = cur;
      even = even.next;
    }
    cur = cur.next;
    i += 1;
  }
  even.next = null;
  odd.next = evenDummy.next;
  return oddDummy.next;
}

export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

export function oddEvenList(head: ListNode | null): ListNode | null {
  const oddDummy = new ListNode(0);
  const evenDummy = new ListNode(0);
  let odd = oddDummy;
  let even = evenDummy;
  let cur = head;
  let i = 1;
  while (cur) {
    if (i % 2 === 1) {
      odd.next = cur;
      odd = odd.next;
    } else {
      even.next = cur;
      even = even.next;
    }
    cur = cur.next;
    i += 1;
  }
  even.next = null;
  odd.next = evenDummy.next;
  return oddDummy.next;
}

Template connection

Partition / group-nodes shape of Linked List Manipulation: two dummy tails, link at the end. The in-place version is the same idea without allocating sentinels.

Reflection

Odd nodes and even nodes grow as two tails. Attach the head of the even list to the end of the odd list.
The even tail must end at null. If it does not, the even list cycles back into the odd list.
An empty list and a single node are themselves. With an even count, the last even node is appended after the odd tail.