Merge Sort Solution (C++)


  • 0
    M

    Typically, merge sort consumes O(n) space when merging two sorted sub-arrays, because it needs an temporary array for merging result.

    But when it comes to single linked list, we don't need extra space. This is why merge sort works perfectly for this problem.

    class Solution {
    
    private:
        int getLength(ListNode* head) {
            ListNode* p = head;
            int result = 0;
            while (p != nullptr) {
                result++;
                p = p->next;
            }
            return result;
        }
    
    private:
        ListNode* split(ListNode* head) {
            int halfLen = getLength(head) / 2;
            ListNode* p = head;
            for (int i = 0; i < halfLen - 1; i++) {
                p = p->next;
            }
            ListNode* p_before = p;
            p = p->next;
            p_before->next = nullptr;
            return p;
        }
    
    private:
        ListNode* merge(ListNode* head_1, ListNode* head_2) {
            if (head_1 == nullptr) {
                return head_2;
            }
            if (head_2 == nullptr) {
                return head_1;
            }
            ListNode* p_1 = head_1;
            ListNode* p_2 = head_2;
            ListNode* head_new = nullptr;
            ListNode* p_new = nullptr;
            if (p_1->val < p_2->val) {
                head_new = p_new = p_1;
                p_1 = p_1->next;
            }
            else {
                head_new = p_new = p_2;
                p_2 = p_2->next;
            }
            while (p_1 != nullptr && p_2 != nullptr) {
                if (p_1->val < p_2->val) {
                    p_new->next = p_1;
                    p_1 = p_1->next;
                }
                else {
                    p_new->next = p_2;
                    p_2 = p_2->next;
                }
                p_new = p_new->next;
            }
            if (p_1 == nullptr) {
                p_new->next = p_2;
            }
            else {
                p_new->next = p_1;
            }
            return head_new;
        }
    
    public:
        ListNode* sortList(ListNode* head) {
            if (getLength(head) <= 1) {
                return head;
            }
            ListNode* half = split(head);
            ListNode* head_sorted = sortList(head);
            ListNode* half_sorted = sortList(half);
            return merge(head_sorted, half_sorted);;
        }
    
    };

Log in to reply
 

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