#328 - Odd Even Linked List

MediumLinked List

Given the head of a singly linked list, group all nodes at odd indices together followed by all nodes at even indices (1-indexed). The relative order inside each group must stay the same. Must use O(1) extra space and O(n) time.

Input	Output
[1,2,3,4,5]	[1,3,5,2,4]
[2,1,3,5,6,4,7]	[2,3,6,7,1,5,4]

Solution Space

Try it

/**
 * Reorders list so odd-indexed nodes come before even-indexed nodes (1-indexed).
 * Maintains two sub-chains and stitches them together.
 *
 * @param head Head of the linked list
 * @returns Head of the reordered list
 */
export function oddEvenList(head: ListNode | null): ListNode | null {
  if (!head || !head.next) return head;

  let odd: ListNode = head;
  let even: ListNode | null = head.next;
  const evenHead: ListNode = even; // save start of even chain

  while (even && even.next) {
    odd.next = even.next; // link odd to next odd
    odd = odd.next;
    even.next = odd.next; // link even to next even
    even = even.next;
  }

  // Connect end of odd chain to beginning of even chain
  odd.next = evenHead;

  return head;
}

Approach: two-pointer relink – maintain an odd pointer and an even pointer; on each iteration advance both by relinking their `.next`. Finally, attach the even sub-list after the odd sub-list.

Time: O(n) – single pass through the list.

Space: O(1) – only a few pointer variables.

#206 Reverse Linked List

#2095 Delete the Middle Node of a Linked List