My C++ solution: use two dummy nodes

  • 0

    Use two dummy nodes to track the heads of the even/odd half links. Split and reconnect them. O(N) time and O(1) space.

    class Solution {
        ListNode* oddEvenList(ListNode* head) {
            ListNode *tail[2], dummyE(0), dummyO(0); 
            int i;
            tail[0] = &dummyE;
            tail[1] = &dummyO;
                tail[i%2] = tail[i%2]->next = head; // split into two half
                head = head->next;
            tail[0]->next =; // reconnect the link
            tail[1]->next = nullptr;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.