Simple C++ 12ms Solution with explanation.


  • 0
     ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
           
            if(l1==NULL)
            return l2;
            
            if(l2==NULL)
            return l1;
            
            //The head of the new mergeList.
            ListNode* head;
            //ListNode *cur point to the smaller node of two lists.
            ListNode* cur=new ListNode(0);
            
            //Point *head to the first *cur to save the head of new list.
            //Because *cur will move(cur=cur->next) during the loop. 
            head=cur;
            
            while(l1!=NULL&&l2!=NULL){
            //Who is smaller, who move forward, until one of lists is empty.    
            if(l1->val<=l2->val){
                cur->next=l1;
                l1=l1->next;
            }else{
                cur->next=l2;
                l2=l2->next;
            }
            cur=cur->next;
            }
            
            if(l1==NULL)
            cur->next=l2;
            
            if(l2==NULL)
            cur->next=l1;
           
           //Reminder, head needs to move 1 step forward.
            return head->next;
        }
    

    Update(08/08/2017): Review and refine.

        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
            if(!l1 || !l2) return l1 ? l1 : l2;
            ListNode head(0);
            ListNode* cur = &head;
            while(l1 && l2){
                if(l1->val < l2->val){
                    cur->next = l1;
                    l1 = l1->next;
                }
                else{
                    cur->next = l2;
                    l2 = l2->next;
                }
                cur = cur->next;
            }
            cur->next = l1 ? l1 : l2;
            return head.next;
        }
    

Log in to reply
 

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