C++ solution merge sort


  • 0
    X
    //sort list
    class Solution {
    public:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
            if (l1 == NULL) return l2;
            if (l2 == NULL) return l1;
            if (l1->val < l2->val) {
                l1->next = mergeTwoLists(l1->next, l2);
                return l1;
            } else {
                l2->next = mergeTwoLists(l1, l2->next);
                return l2;
            }
        }
        
        ListNode* sortList(ListNode* head) {
            if (NULL == head) return NULL;
            ListNode * p = head;
            int size = 0;
            while (p != NULL) {p = p->next; size++;}
            return mergeSortList(head, size);
        }
        
        ListNode* mergeSortList(ListNode* head, int size) {
            if (size == 1) return head;
            int halfSize = size / 2;
            int theOtherHalf = size - halfSize;
            
            ListNode * p = head;
            int index = 1;
            while (index < halfSize) {
                p = p->next; index++;
            }
            
            ListNode * theOtherHalfHead = p->next;
            p->next = NULL;
            
            head = mergeSortList(head, halfSize);
            theOtherHalfHead = mergeSortList(theOtherHalfHead, theOtherHalf);
            return mergeTwoLists(head, theOtherHalfHead);
        }
    };

Log in to reply
 

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