used merge , CPP 59ms


  • 0
    F

    class Solution {
    public:
    ListNode* sortList(ListNode* head) {

        if(head == NULL || head->next == NULL)
        {
            return head;
        }
        
        ListNode* slow = getMid(head);
        ListNode* headTwo = slow->next;
        slow->next = NULL;
        
        ListNode* p = sortList(head);
        ListNode* q = sortList(headTwo);
        return merge(p,q);
    }
    
    ListNode* getMid(ListNode* head)
    {     
        ListNode* slow = head;
        ListNode* fast = head;
        
          while(fast->next != NULL && fast->next->next != NULL)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    
    ListNode* merge(ListNode* p , ListNode* q)
    {
         ListNode* r = new ListNode(0);
        ListNode* s = r;
        
        while(p != NULL && q != NULL)
        {
            if(p->val < q->val)
            {
                s->next = p;
                p = p->next;
                s = s->next;
            }
            else
            {
                s->next = q;
                q = q->next;
                s = s->next;
            }
        }
        
        if(p != NULL)
        {
            s->next = p;
        }
        
        if(q != NULL)
        {
            s->next = q;
        }
        
        ListNode* t = r->next;
        delete r;
        return t;
    }
    

    };


Log in to reply
 

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