14 line clean C++ Solution


  • 126
    X
    class Solution {
    public:
        ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
            ListNode dummy(INT_MIN);
            ListNode *tail = &dummy;
            
            while (l1 && l2) {
                if (l1->val < l2->val) {
                    tail->next = l1;
                    l1 = l1->next;
                } else {
                    tail->next = l2;
                    l2 = l2->next;
                }
                tail = tail->next;
            }
    
            tail->next = l1 ? l1 : l2;
            return dummy.next;
        }
    };

  • 0
    L

    Question, if l1 is more than 1 nodes longer than l2. This may not work. Am I right?


  • 0
    X

    Probably not. This code works regardless of l1 and l2's lengths. Can u give a concrete counter-example where it fails?


  • 0
    L

    Sorry, I think your right. :)


  • 0
    H
    This post is deleted!

  • -11
    H
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2){
    		if (l1 == NULL)
    			return l2;
    		if (l2 == NULL)
    			return l1;
    		ListNode *small = l1->val < l2->val ? l1 : l2;
    		ListNode *large = l1->val >= l2->val ? l1 : l2;
    		while (small->next){
    			if (small->next->val < large->val)
    				small = small->next;
    			else{
    				ListNode *temp = small->next;
    				small->next = large;
    				small = large;
    				large = temp;
    			}
    		}
    		small->next = large;
    		return l1->val < l2->val ? l1 : l2;
    	}

  • 0
    Z

    beautiful code, but what is the function of dummy(),thank you!


  • 3
    I

    Dummy is there to store a pointer to the new head of the list. Tail starts off as what will be the head, but it changes, so dummy stores the pointer to the head.


  • 2
    F

    JAVA version

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            if(l1 == null || l2 == null ) {
                return l1 == null ? l2 : l1;
            }
            ListNode dummy = new ListNode(0);
            ListNode current = dummy;
            while(l1 != null && l2 != null ) {
                if(l1.val < l2.val ) {
                    current.next = l1;
                    l1 = l1.next;
                }
                else {
                    current.next = l2;
                    l2 = l2.next;
                }
                current = current.next;
            }
            current.next = l1 == null ? l2 : l1;
            return dummy.next;
        }
    }
    

  • 3

    I think everyone forgot about the condition :
    Merge two sorted linked lists and return it as "A NEW LIST".

    However, the checker did not check for that in this program.


  • 0
    Q

    what did the dumpy function do ? thanks.


  • 1
    R

    @Yuan-Yen This works.
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode* l3 = new ListNode(0);
    ListNode *l4;
    l4=l3;
    if(!l1)
    return l2;
    if(!l2)
    return l1;

        while(l1 && l2)
        {
            if(l1->val < l2->val)
            {
                l3->next =  new ListNode(l1->val);
                l1 = l1->next;
            }
            else
            {
                l3->next = new ListNode(l2->val);
                l2 = l2->next;
            }
            l3=l3->next;
        }
        
        while(l1)
        {
            l3->next = new ListNode(l1->val);
            l1 = l1->next;
            l3=l3->next;
    
        }
        
        while(l2)
        {
           l3->next = new ListNode(l2->val);
           l2 = l2->next;
           l3=l3->next;
    
        }
        
        return l4->next;
    }

  • 0
    T

    @xiaohui7 beautiful use of dummy node in the beginning! It takes me many lines of code to take care of the initialization.


  • 1
    L

    It can be simpler:

        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
            ListNode dummy(0);
            ListNode *tail = &dummy;
            while(l1 && l2) {
                ListNode *& node = l1->val < l2->val ? l1 : l2;
                tail = tail->next = node;
                node = node->next;
            }
            tail->next = l1 ? l1 : l2;
            return dummy.next;
        }
    

    P.S. I didn't know I can reference a value of the "?:" expression :P But when I try it worked!


  • 0
    W

    The use of dummy helps in simplifying initialization code greatly. If its not forced upon that new lists should only reuse nodes from existing lists, the solution is good.


  • 0
    H

    I get the approach where dummy is initialized but the actual list we return starts from the next node. However; I don't see how dummy.next isn't NULL? Does modifying tail->next in the first iteration also change dummy.next? (I still struggle with pointers...)


  • 0
    C

    Beautiful solution ! Especially at the end..


  • 1
    L

    Actually you need free the first node memory before the function return. just like this:

    tail = dummy;
    dummy = dummy->next;
    delete tail
    return dummy
    

  • 0
    D

    8-line version of it :)

    struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
        struct ListNode l3_head;
        struct ListNode * l3_tail = &(l3_head);
        while(l1 != NULL && l2 != NULL ){
            l3_tail = l3_tail->next = (l1->val <= l2->val)? l1 : l2;
            void * dummy = (l1->val <= l2->val)? (l1 = l1->next) : (l2 = l2->next);
        }
        l3_tail->next = (l1 != NULL)? l1 : l2;
        return l3_head.next;
    }
    

  • 2
    S

    @xiaohui7 I think this solution is not quite right... We are supposed to focus on "a new list". Otherwise,if we need to delete the new list, the old one will be affected too...


Log in to reply
 

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