Reorder Nodes by Odd/Even Index

medium linked list pointers

Problem

Group all nodes at odd positions (1st, 3rd, 5th, …) before all nodes at even positions, preserving the relative order within each group. Use two interleaved chains and stitch them together at the end.

Input1 → 2 → 3 → 4 → 5 → null

Output1 → 3 → 5 → 2 → 4 → null

Odd-index nodes first (1, 3, 5), then even-index nodes (2, 4).

node values (comma-separated)

def odd_even(head):
    if head is None: return None
    odd, even = head, head.next
    even_head = even
    while even and even.next:
        odd.next = even.next
        odd = odd.next
        even.next = odd.next
        even = even.next
    odd.next = even_head
    return head

function oddEven(head) {
  if (!head) return null;
  let odd = head, even = head.next, 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;
}

class Solution {
    public ListNode oddEven(ListNode head) {
        if (head == null) return null;
        ListNode odd = head, even = head.next, 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;
    }
}

ListNode* oddEven(ListNode* head) {
    if (!head) return nullptr;
    ListNode *odd = head, *even = head->next, *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;
}

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