
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; }
}

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; }
C++ 2 solutions


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; } };

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).