Odd Even Linked List

medium linked list pointers

Problem

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list. The first node is considered odd, and the second node is even, and so on.

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_list(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 oddEvenList(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 oddEvenList(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* oddEvenList(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;
}

Explanation

We want all the odd-position nodes first, then all the even-position nodes. The neat trick is to weave two chains at the same time: one chain of odd nodes and one chain of even nodes, then stitch the even chain onto the end of the odd chain.

We keep an odd pointer (starting at the head) and an even pointer (starting at the second node), and remember even_head so we can reattach the even part later. In each loop step we let odd skip over the even node to grab the next odd node, then let even do the same to grab the next even node.

It works because every other node belongs to each chain. By always jumping two ahead, odd collects positions 1, 3, 5, … and even collects positions 2, 4, 6, …. When we finish, odd.next = even_head joins them.

Example: 1 → 2 → 3 → 4 → 5. Odd chain becomes 1 → 3 → 5, even chain becomes 2 → 4. Linking them gives 1 → 3 → 5 → 2 → 4.

All of this is done by re-pointing existing links, so it runs in one pass with only constant extra memory.

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