My C++ solution (recursive merge sort)


  • 0
    D

    The basic idea is to 1) split the list by half, 2) merge sort each of the half lists, and 3) merge two sorted half lists. The below version is based on recursion but as pointed out by other great programmers, a non-recursive version of merge sort is also possible but more involved.

    class Solution {
    public:
        ListNode *sortList(ListNode *head) {
    
         ListNode *head2;
         if(!head ||!head->next)
         {// if the list is empty or only has one node, just return
             return head;
         }
         else
         {// split the list by half, sort each of them and merge the two half lists
             head2 = splitList(head);
             return mergeList(sortList(head), sortList(head2));
         }
        }
     
        // split the list (with length >= 2) in half, and return the head of the second half list
        ListNode *splitList(ListNode *head) {
            ListNode *fastP, *slowP, *newHead;
            fastP = head->next->next;
            slowP = head;
            while(fastP && fastP->next)
            {
                fastP = fastP->next->next;
                slowP = slowP->next;
            }
            newHead = slowP->next;
            slowP->next = NULL;
            
            return newHead;
        }
        
        // merge two lists, 
        ListNode *mergeList(ListNode *head1, ListNode *head2) {
            
            ListNode *newHead = head1, *pNode;
            
            if(!head2)
            {
                return head1;
            }
            else if(!head1)
            {
                return head2;
            }
            else
            {// both list1 and list2 are non-empty
                if(head1->val > head2->val)
                {
                    newHead = head2;
                    head2 = head1;
                    head1 = newHead;
                }
                while(head2)
                {
                    while( head1->next && (head1->next)->val <= head2->val)
                    {
                        head1 = head1->next;
                    }
                    pNode = head1->next;
                    head1->next = head2;
                    head2 = pNode;
                }// while
                return newHead;
            }// else
        }
    
    };

  • 0
    N

    split split split........ O(n^2) from split


Log in to reply
 

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