Odd Even Linked List

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, the second even, and so on. Relative order within each group must be preserved.

Practice Link

Examples#

Example 1: head = [1,2,3,4,5]

Output: [1,3,5,2,4]

Example 2: head = [2,1,3,5,6,4,7]

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

Two-Pointer Weave#

Maintain two pointers — p (tail of the odd chain) and q (tail of the even chain) — and a qHead anchor so the even chain can be appended at the end. Each iteration simultaneously extends the odd chain by one node and the even chain by one node, advancing both pointers. Loop on q && q->next so that after the loop p is always the last odd node and p->next = qHead safely stitches the two chains.

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (!head) return nullptr;
        if (!head->next) return head;

        ListNode* p = head;        // tail of odd chain
        ListNode* q = head->next;  // tail of even chain
        ListNode* qHead = q;       // head of even chain (anchor)

        while (q && q->next) {
            p->next = q->next;     // odd skips over even
            p = p->next;           // advance odd tail

            q->next = p->next;     // even skips over odd
            q = q->next;           // advance even tail
        }
        p->next = qHead;           // stitch: last odd → first even

        return head;
    }
};

Time Complexity: O(n) — single pass
Space Complexity: O(1) — only pointer variables, no extra allocation

Why loop on q && q->next not p && p->next#

Looping on p causes p to become nullptr inside the loop for even-length lists (e.g. [1,2]). The loop exits, and p->next = qHead then crashes.

Looping on q && q->next guarantees the loop exits only when:

• q is null — list had odd length, p is the last node ✓
• q->next is null — list had even length, p is the second-to-last node (the last odd node) ✓

In both cases p is non-null when we reach p->next = qHead.