Simple yet best solution using MergeSort in C++


  • 0
    class Solution {
    private:
        ListNode* merge(ListNode* A, ListNode* B)
        {
            static ListNode newHead(0);
            ListNode *t = &newHead, *pA = A, *pB = B;
            while(pA || pB)
            {
                if(!pB || (pA && pA->val < pB->val))
                {
                    t->next = pA;
                    pA = pA->next;
                    t = t->next;
                }
                else
                {
                    t->next = pB;
                    pB = pB->next;
                    t = t->next;
                }
            }
            t->next = NULL;
            return newHead.next;
        }
    public:
        ListNode* sortList(ListNode* head) {
            if(!head || !head->next) return head;
            ListNode *slow = head, *fast = head->next, *r = NULL;
            while(fast && fast->next)
            {
                slow = slow->next;
                fast = fast->next->next;
            }
            r = slow->next; //store the right head pointer;
            slow->next = NULL;  //terminate the left;
            return merge(sortList(head), sortList(r));
        }
    };

Log in to reply
 

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