C++ 2 solutions


  • 3
    4
    1. Mutable, recursive

      ListNode * mergeTwoLists( ListNode * l1, ListNode * l2 )
      {
      if( !l1 ) return l2;
      if( !l2 ) return l1;

       if( l1->val < l2->val )
       { 
           l1->next = mergeTwoLists( l1->next, l2 );
           return l1;
       }
       else
       {
           l2->next = mergeTwoLists( l1, l2->next );
           return l2;
       }
      

      }

    2. New list, iterative

      ListNode * mergeTwoLists( ListNode * l1, ListNode * l2 )
      {
      if( !l1 ) return l2;
      if( !l2 ) return l1;

           int min = l1->val;
           if( min > l2->val)
           {
               min = l2->val;
               l2 = l2->next;
           }
           else l1 = l1->next;
           
           ListNode * out =new ListNode( min );
           ListNode * next = out;
           
           for( ;; )
           {
               if( l1 && l2 )
               {
                   min = l1->val;
                   if( min > l2->val)
                   {
                       min = l2->val;
                       l2 = l2->next;
                   }
                   else l1 = l1->next;
                   ListNode * temp =new ListNode( min );
                   
                   next->next = temp;
                   next=next->next;
               }
               else if( l1 )
               {
                   ListNode * temp =new ListNode( l1->val );
                   next->next = temp;
                   next = next->next;
                   l1 = l1->next;
               }
               else if( l2 )
               {
                   ListNode * temp =new ListNode( l2->val );
                   next->next = temp;
                   next = next->next;
                   l2 = l2->next;
               }
               else break;
           }
           return out;
       }

  • 0
    L

    Actually, In solution 2, u don't need to new nodes, and can be impoved.

    class Solution {
    public:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
            ListNode *l3, *head;
            head = l3;
            if(l1 == NULL and l2 == NULL)return NULL;
            if(l1 == NULL or l2 == NULL)return l1==NULL?l2:l1;
            while(l1 and l2){
                if(l1->val <= l2->val){
                    l3->next = l1;
                    l1 = l1->next;
                    l3 = l3->next;
                }
                else {
                    l3->next = l2;
                    l2 = l2->next;
                    l3 = l3->next;
                }
            }
            if(l1){//just point to the left nodes if there have.
                l3->next = l1;
            }
            if(l2){
                l3->next = l2;
            }
            return head->next;
        }
    };

  • 0
    V

    Good answer.


  • 0

    hello,after reading your codes,there may be some errors in your codes I think.It is theinitialization of l3 that may cause mistake,because at first ,your l3(pointer of ListNode) does not point to a real space of ListNode in memory,so when you begin running "l3->next=l1",it may cause mistake,l3 is just a pointer,but we can not find its real space in memory,so you may construct only one ListNode and make l3 be its point,(I am awfully sorry for my poor English).


  • 0
    L

    yeah, u are right. New a empty node to initialize l3 and head.顺带,我能看懂中文啊!哈哈哈哈哈哈哈哈


Log in to reply
 

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