Merge Two Sorted ListsMar 30 '12
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
This is an algorithm with O(n) time complexity. List L2 is merged in list L1 and returned as a new list.
More compact solution:
ReplyDeleteclass Solution {
public:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
if(l1==NULL)
return l2;
else if(l2==NULL)
return l1;
if(l1->val<=l2->val){
l1->next=mergeTwoLists(l1->next,l2);
return l1;
}
else{
l2->next=mergeTwoLists(l1,l2->next);
return l2;
}
}
};