My solution based on C++


  • 1
    M
    ListNode *sortList(ListNode *head) {
        if (head == NULL || head->next == NULL)
            return head;
            
        // find the middle place
        ListNode *p1 = head;
        ListNode *p2 = head->next;
        while(p2 && p2->next) {
            p1 = p1->next;
            p2 = p2->next->next;
        }
        p2 = p1->next;
        p1->next = NULL;
        
        return mergeList(sortList(head), sortList(p2));
    }
    
    ListNode *mergeList(ListNode* pHead1, ListNode* pHead2) {
        if (NULL == pHead1)
            return pHead2;
        else if (NULL == pHead2)
            return pHead1;
        
        ListNode* pMergedHead = NULL;
    
        if(pHead1->val < pHead2->val)
        {
            pMergedHead = pHead1;
            pMergedHead->next = mergeList(pHead1->next, pHead2);
        }
        else
        {
            pMergedHead = pHead2;
            pMergedHead->next = mergeList(pHead1, pHead2->next);
        }
    
        return pMergedHead;
    }

  • 0
    H

    will it be a constant space?? Since you are using recursion.


Log in to reply
 

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