C++ merge sort solution


  • 0
    Z
    class Solution {
    public:
        ListNode *merge(ListNode *a, ListNode *b) {
            if (!a) return b;
            if (!b) return a;
            
            ListNode *tmp;
            if (a->val < b->val) {
                tmp = a;
                tmp->next = merge(a->next, b);
            } else {
                tmp = b;
                tmp->next = merge(a, b->next);
            }
            return tmp;
        }
        
        ListNode *split(ListNode *a) {
             if (!a) return NULL;
             ListNode *p1 = a;
             ListNode *p2 = a;
             while (p1->next && p2->next && p2->next->next) {
                 p1 = p1->next;
                 p2 = p2->next->next;
             }
             ListNode *t = p1;
             p1 = p1->next;
             t->next = NULL;
             return p1;
        }
        
        ListNode* sortList(ListNode* head) {
            if (!head) return NULL;
            if (!head->next) return head;
            ListNode *p1 = head;
            ListNode *p2 = split(head);
            return merge(sortList(p1), sortList(p2));
        }
    };
    

Log in to reply
 

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