C++ standard Merge Sort solution


  • 0
    B

    Two techniques used in this problem.

    1. slow/fast pointers to find the middle of the list
    2. dummy head to help merge
    class Solution {
    public:
        ListNode* mergeSortedLinkedList(ListNode* l1, ListNode* l2) {
            ListNode *head = new ListNode(0), *cur = head;
            while(l1 && l2) {
                if(l1->val > l2->val) {
                    cur->next = l2;
                    l2 = l2->next;
                } else {
                    cur->next = l1;
                    l1 = l1->next;
                }
                cur = cur->next;
            }
            if(l1) cur->next = l1;
            else if(l2) cur->next = l2;
            cur = head->next;
            delete head;
            return cur;
        }
        ListNode* sortList(ListNode* head) {
            if(!head || !head->next) return head;
            ListNode* slow = head, *fast = head;
            while(fast->next && fast->next->next) {
                slow = slow->next;
                fast = fast->next->next;
            }
            fast = slow->next;
            slow->next = nullptr;
            slow = head;
            ListNode *left = sortList(slow);
            ListNode *right = sortList(fast);
            return mergeSortedLinkedList(left, right);
        }
    };
    

Log in to reply
 

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