My 10-line clean C++ code


  • 22
    D

    The basic idea is to use a dummy node to track the new header and move the cur pointer forward along the list with a smaller node value; and switch two lists when the current list has a larger value than the other one

    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        dummy.next = l1;
        ListNode *cur = &dummy;
        
        while(l2)
        {
            while(cur->next && cur->next->val<=l2->val) cur = cur->next; // if the current list, l1, has a smaller value, then move cur forward
            l1 = cur->next; // otherwise, switch l1 and l2
            cur->next = l2;
            l2 = l1;
        }
        return dummy.next;
    }

  • 1
    C

    Brilliant code! Actually this can be regarded as the iterative code of the recursive method:
    https://leetcode.com/discuss/8372/a-recursive-solution

    1 the uncertainty of the head is handled through the dummy node. the uncertainty of next element is handled by the switching between two lists.

    2 each iteration here is equivalent to several recursive calls in the recursive methods until the switching is needed.


Log in to reply
 

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