My C++ solution: use two dummy nodes


  • 0
    D

    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 {
    public:
        ListNode* oddEvenList(ListNode* head) {
            ListNode *tail[2], dummyE(0), dummyO(0); 
            int i;
            tail[0] = &dummyE;
            tail[1] = &dummyO;
            for(i=0;head!=nullptr;++i)
            {
                tail[i%2] = tail[i%2]->next = head; // split into two half
                head = head->next;
            }
            tail[0]->next = dummyO.next; // reconnect the link
            tail[1]->next = nullptr;
            return dummyE.next;
        }
    };

Log in to reply
 

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