C++ O(n) time and O(1) space solution. Easy to understand


  • 0
    S

    Here you will simply need to pull the item from the main list and append it to whether new list of odds or evens.

    ListNode* oddEvenList(ListNode* head)
        {
            if (head == NULL || head->next == NULL)
                return head;
                
            ListNode *oddHead = NULL;
            ListNode *oddTail = NULL;
            
            ListNode *evenHead = NULL;
            ListNode *evenTail = NULL;
            
            bool isOdd = true;
            
            ListNode *runner = head;
            while (runner != NULL)
            {
                // pull the item from the main list
                ListNode *item = runner;
                runner = runner->next;
                item->next = NULL;
                
                // push it in whether odds or evens
                if (isOdd)
                {
                    if (oddHead == NULL)
                    {
                        oddHead = item;
                        oddTail = item;
                    }
                    else
                    {
                        oddTail->next = item;
                        oddTail = item;
                    }
                }
                else
                {
                    if (evenHead == NULL)
                    {
                        evenHead = item;
                        evenTail = item;
                    }
                    else
                    {
                        evenTail->next = item;
                        evenTail = item;
                    }
                }
                
                isOdd = !isOdd;
            }
            
            // now concat odd and even
            oddTail->next = evenHead;
            
            return oddHead;
        }
    

Log in to reply
 

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