328 - Odd Even Linked List

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, the second even, and so on. The relative order inside both groups must stay as it was in the input.

Input: head = [1,2,3,4,5]
Output: [1,3,5,2,4]

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

Constraints:

• 0 <= n <= 10^4
• -10^6 <= Node.val <= 10^6
• Must run in O(1) extra space and O(n) time

The indices are positions, not values — the second example is the giveaway, since 2 is even but sits at position 1 and stays at the front.

Approach

The output is two runs of the original list interleaved apart: positions 1,3,5,… then 2,4,6,…, each in their original order. Both chains are being built from the same forward walk, so keep a pointer at the end of each. odd sits on the last odd node and even on the last even node, and each one reaches its next member by skipping over the other:

1 -> 2 -> 3 -> 4 -> 5
^    ^
odd  even

odd->next = even->next      1 -> 3        odd hops over 2
even->next = odd->next      2 -> 4        even hops over 3

1 -> 3 -> 5        2 -> 4
          ^             ^
          odd           even

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head;
        ListNode* odd = head;
        ListNode* even = head->next;
        ListNode* 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) - one pass, each node rewired once
• space: O(1) - three pointers, nodes relinked in place