# LeetCode: Merge Two Sorted Lists



## Leetcode Problem

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.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4


## Explanation

The logic is simple, iterate both link list nodes, compare the value of nodes and add the next to result.

Use dummy node for simplifying the code, and another corner case is if a link list is longer than the other one.

Assume the length of two link list is M and N, the time complexity is $$O(Max(M, N))$$.

### Naive Version class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(0);
if(l1 == NULL) return l2;
if(l2 == NULL) return l1;

ListNode* cur = dummy;
while(l1 && l2) {
if(l1->val < l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}

if(l1) cur->next = l1;
if(l2) cur->next = l2;
return dummy->next;
}
};


### Recursive version

Another solution is using recursive iteration, the corner case is handled by the first two if test.

class Solution {
public:
void mergeTwoLists_iter(ListNode* l1, ListNode* l2, ListNode* cur) {
if(l1 == NULL) { cur->next = l2; return; }
if(l2 == NULL) { cur->next = l1; return; }

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

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(0);
mergeTwoLists_iter(l1, l2, dummy);
return dummy->next;
}
};

Last Updated on