My Clear Merge Sort Solution with Detailed Explanation C++ time: O(nlogn) space: O(1)


  • 0
    E
    class Solution {
    public:
        ListNode* sortList(ListNode* head) {
    // corner check if head is NULL or there is only one node, sorting is not neccessary.
            if (!head || !head->next) {
                return head;
            }
    // preparation for merge sort finding the mid of the list       
            ListNode* mid = findMid(head);
    // seperate one list to two 
            ListNode* right = mid->next;
    // add NULL to the first half list
            mid->next = NULL;
    
    // recursively sort two lists   
            head = sortList(head);
            right = sortList(right);
    
    // merge two lists      
            return mergeList(head, right);
        }
    private:
        ListNode* mergeList(ListNode* left, ListNode* right) {
            if (!left){
                return right;
            }
            if (!right) {
                return left;
            }
    // define a dummy node to link all the nodes from two lists in ascending order.
            ListNode* dummy = new ListNode(0);
            ListNode* cur = dummy;
            while (left && right) {
                if (left->val < right->val) {
                    cur->next = left;
                    left = left->next;
                } else {
                    cur->next = right;
                    right = right->next;
                }
                cur = cur->next;
            }
            while (left) {
                cur->next = left;
                left = left->next;
                cur = cur->next;
            }
            while (right) {
                cur->next = right;
                right = right->next;
                cur = cur->next;
            }
            return dummy->next;
        }
    // helper fuction use two pointers to find the left mid of the list.
        ListNode* findMid(ListNode* list) {
            if (!list) {
                return list;
            }
            ListNode* walker = list;
            ListNode* runner = list->next;
            while (runner && runner->next) {
                walker = walker->next;
                runner = runner->next->next;
            }
            return walker;
        }
    };
    

    Time complexity is O(nlogn), n is the number of nodes on the linked list
    Space complexity is O(1)


  • 1
    A

    @EvanPerlinHu Recursive is not O(1) space.


Log in to reply
 

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