Sharing my O(n) solution in c++, AC-2015.04.29


  • 0
    Z

    class Solution
    {

    public:
    void reorderList(ListNode *head) {
    if (nullptr == head || nullptr == head->next) {
    return ;
    }

        ListNode *pfast = head->next, *pslow = head;
        while (pfast) {
            pfast = (pfast->next) ? pfast->next->next : nullptr;
            pslow = pslow->next;
        }
        
        ListNode *pbeg1 = head, *pbeg2 = reverseList(pslow->next);
        pslow->next = nullptr;
        
        head = mergeTwoList(pbeg1, pbeg2);
    }
    

    private:
    ListNode *reverseList(ListNode *head) {
    if (nullptr == head || nullptr == head->next) {
    return head;
    }

        ListNode *pret = nullptr, *p = head, *pNext = head;
        while (p) {
            pNext = p->next;
            
            p->next = pret;
            pret = p;
            p = pNext;
        }
        
        return pret;
    }
    
    ListNode *mergeTwoList(ListNode *ph1, ListNode *ph2) {
        if (nullptr == ph1 && nullptr == ph2) {
            return nullptr;
        }
        
        if (nullptr == ph1) {
            return ph2;
        }
        if (nullptr == ph2) {
            return ph1;
        }
        
        ListNode *pret = new ListNode(-1), *p = pret;
        ListNode *p1 = ph1, *p2 = ph2;
        bool is_p1 = true;
        while (p1 && p2) {
            if (is_p1) {
                p->next = p1;
                p1 = p1->next;
                is_p1 = false;
            } else {
                p->next = p2;
                p2 = p2->next;
                is_p1 = true;
            }
            
            p = p->next;
        }
        
        p->next = nullptr;
        p->next = (p1) ? p1 : p->next;
        p->next = (p2) ? p2 : p->next;
        
        return pret->next;
    }
    

    };


Log in to reply
 

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