C solution (19ms) - using merge sort


  • 4

    We use Merge Sort to tackle this problem:

    • Split the list into half. Use fast/slow pointer to get to the middle of the list.
    • Recursively sort the two independent lists.
    • Use Merge Two Sorted Lists to merge the two sorted lists (left and right) together.
    • Return the new merged list as the sorted list.
    struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2);
    
    struct ListNode* sortList(struct ListNode* head) {
        if (!head || !head->next) return head;
        struct ListNode *slow = head, *fast = head, *prev, *left, *right;
        while (fast && fast->next) {
            prev = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        prev->next = NULL;
        left = sortList(head);
        right = sortList(slow);
        return mergeTwoLists(left, right);
    }
    
    struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
        struct ListNode dummyHead = {0}, *prev = &dummyHead;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                prev->next = l1;
                l1 = l1->next;
            } else {
                prev->next = l2;
                l2 = l2->next;
            }
            prev = prev->next;
        }
        if (l1) prev->next = l1; else prev->next = l2;
        return dummyHead.next;
    }
    

Log in to reply
 

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