Transparent C++ solution, 12 ms, one pass, O(1) space, edge cases handled nicely


  • 1
    X

    I have not encountered a solution on the web which would utilize a simple idea of swapping the source and destination lists whenever the current element in the destination list becomes greater than the current value in the source list (pivot). Doing it this way we always maintain the invariant that destination is less than source, and just traverse the pointers forwards, whatever the actual underlying list is.

    I believe this one is quite nice and would be useful for people here.

    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == NULL)
        {
            return l2;
        }
        if(l2 == NULL)
        {
            return l1;
        }
        
        if(l2->val < l1->val)
        {
            swap(l1, l2);
        }
        ListNode dummy(0);
        dummy.next = l1;
        ListNode* prev = &dummy;
        while(l1)
        {
            if(l1->val > l2->val)
            {
                prev->next = l2;
                swap(l1, l2);
            }
            prev = l1;
            l1 = l1->next;
        }
        prev->next = l2;
    
        return dummy.next;
    }

Log in to reply
 

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