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.
Solution 1: Iterative O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// Author: Huahua class Solution { public: Solution 1: Iterative ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode dummy(0); 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; } if(l1) tail->next = l1; if(l2) tail->next = l2; return dummy.next; } }; |
Solution 2: Recursive O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { // If one of the list is emptry, return the other one. if(!l1 || !l2) return l1 ? l1 : l2; // The smaller one becomes the head. if(l1->val < l2->val) { l1->next = mergeTwoLists(l1->next, l2); return l1; } else { l2->next = mergeTwoLists(l1, l2->next); return l2; } } }; |