Without using the extra space

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

        ListNode* even = head->next;
        ListNode* odd = head;
        ListNode*  evenHead = head->next;

        while(even && even->next){
            odd->next = even->next;
            odd=odd->next;

            even->next=odd->next;
            even=even->next;
        }

        odd->next=evenHead;
        return head;
    }
};

With help of extra array

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

        // Step 1: Store values in array
        vector<int> values;
        ListNode* curr = head;
        while (curr) {
            values.push_back(curr->val);
            curr = curr->next;
        }

        // Step 2: Reorder values into odd indices first, then even
        vector<int> reordered;
        for (int i = 0; i < values.size(); i += 2) {
            reordered.push_back(values[i]);  // odd positions (1-based)
        }
        for (int i = 1; i < values.size(); i += 2) {
            reordered.push_back(values[i]);  // even positions
        }

        // Step 3: Rebuild the linked list with reordered values
        curr = head;
        for (int val : reordered) {
            curr->val = val;
            curr = curr->next;
        }

        return head;
    }
};