C++ code, O(n) time, O(1) space


  • 0
    C
    class Solution {
    public:
        ListNode* oddEvenList(ListNode* head) 
        {
            if(!head || !head->next) return head;
            
            // odd nodes......    even nodes........  unknown...
            // oddhead   oddtail   evenhead eventail  unknownhead
            
            ListNode *oddhead = head;
            ListNode *oddtail = head;
            
            ListNode *evenhead = head->next;
            ListNode *eventail = head->next;
            
            ListNode *unknownhead = eventail->next;
            while(unknownhead)
            {
                eventail->next = unknownhead->next;
                eventail = eventail->next;
                
                oddtail->next = unknownhead;
                unknownhead->next = evenhead;
                oddtail = unknownhead;
                
                if(eventail) unknownhead = eventail->next;
                else break;
            }
            
            return oddhead;
        }
    };

Log in to reply
 

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