C++ solution with o(n) time and o(1) space, but why time limit exceeded?


  • 0
    C
    class Solution {
    public:
        void reorderList(ListNode *head) {
            if(!head || !head->next || !head->next->next)
                return;
            ListNode* fast = head;
            ListNode* slow = head;
            while(fast->next && fast->next->next)
            {
                fast = fast->next->next;
                slow = slow->next;
            }
            
            ListNode* mid = slow->next;
            slow->next = NULL;
            ListNode* rmid = reverse(mid);
            
            merge(head,rmid);
        }
    private:
        ListNode* reverse(ListNode* head)
        {
            if(!head || !head->next)
                return head;
            ListNode* prev = head;
            ListNode* cur = head->next;
            head->next = NULL;
            ListNode* last = NULL;
            while(cur)
            {
                last = cur->next;
                cur->next = prev;
                prev = cur;
                cur = last;
            }
            
            return prev;
        }
        
        void merge(ListNode* first, ListNode* second)
        {
            if(!first || !second)
                return;
            
            ListNode* cur = first;
            first = first->next;
            cur->next = second;
            cur = second;
            second = second->next;
            while(second && first)
            {
                cur->next = first;
                cur = first;
                cur->next = second;
                cur = second;
                first = first->next;
                second = second->next;
            }
            
            if(second)
                cur->next = second;
            else if(first)
                cur->next = first;
            else
                cur->next = NULL;
                
            return;
        }
    };

Log in to reply
 

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