A very easy to understand merge sort code with O(1) extra space and O(nlogn) time.


  • 0
    N
    
    ListNode *merge(ListNode *a,ListNode *b)
    {
        if(!a)  return b;
        if(!b)  return a;
        ListNode *head = NULL;
        if(a->val<b->val){
            head = a;
            head->next = merge(a->next,b);
        }else{
            head = b;
            head->next = merge(a,b->next);
        }
        return head;
    }
    
    void split(ListNode *&head,ListNode *&a,ListNode *&b)
    {
        if(!head or !head->next){
            a = head;
            b = NULL;
        }else{
            ListNode *slow=head,*fast=head->next;
            while(fast){
                fast = fast->next;
                if(fast){
                    slow = slow->next;
                    fast = fast->next;
                }
            }
            a = head;
            b = slow->next;
            slow->next = NULL;
        }
    }
    
    void mergesort(ListNode *&head)
    {
        ListNode *temp = head;
        if(!temp or !temp->next)  return ;
        ListNode *a=NULL,*b=NULL;
        split(temp,a,b);
        mergesort(a);
        mergesort(b);
        head = merge(a,b);
    }
    
    class Solution {
    public:
        ListNode* sortList(ListNode* head) {
            mergesort(head);
            return head;
        }
    };
    
    

Log in to reply
 

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