c++ O(N)


  • 0
    G
    class Solution {
    public:
        
        pair<ListNode *,ListNode *> reverse(ListNode *head){
            if(head == nullptr || head->next == nullptr){
                return {head,head};
            }
            
            auto p = reverse(head->next);
            p.second->next = head;
            head->next = nullptr;
            return {p.first,head};
        }
    
        ListNode *getMidElement(ListNode *head){
            ListNode *h = head;
            ListNode *fast = head->next->next;
            
            while(fast != nullptr){
                h = h->next;
                fast = fast->next != nullptr ? fast->next->next : nullptr;
            }
            
            return h;
        }
        
        void reorderList(ListNode* head) {
            
            if(head == nullptr || head->next == nullptr){
                return;
            }
            
            ListNode *n = getMidElement(head);
            ListNode *t = n->next;
            n->next = nullptr;
            ListNode *rev = reverse(t).first;
            
            auto currFirst = head;
            auto currRev = rev;
            
            while(currFirst != nullptr && currRev != nullptr){
                auto firstNext = currFirst->next;
                auto revNext = currRev->next;
                
                currFirst->next = currRev;
                currRev->next = firstNext;
                currFirst = firstNext;
                currRev = revNext;
            }
        }
    };
    

Log in to reply
 

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