Leetcode Problem
https://leetcode.com/problems/merge-two-sorted-lists/
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;
}
};
|
Preparing for an interview? Check out this!
