21.Merge-Two-Sorted-Lists
Last updated
Was this helpful?
Last updated
Was this helpful?
Was this helpful?
https://www.lintcode.com/problem/merge-two-sorted-lists
https://leetcode.com/problems/merge-two-sorted-lists
Merge two sorted (ascending) linked lists and return it as a new sorted list. The new sorted list should be made by splicing together the nodes of the two lists and sorted in ascending order.
Intuition
We can achieve the same idea via iteration by assuming that l1
is entirely less than l2
and processing the elements one-by-one, inserting elements of l2
in the necessary places in l1
.
Complexity Analysis
Time complexity : O(n + m)
Space complexity : O(1)
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while (l1 != null && l2 != null) {
if (l1.val > l2.val){
curr.next = l2;
l2 = l2.next;
} else {
curr.next = l1;
l1 = l1.next;
}
curr = curr.next;
}
curr.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
}
Intuition
We can recursively define the result of a merge
operation on two lists as the following (avoiding the corner case logic surrounding empty lists):
list1.next = merge(list1.next, list2) list1.val < list2.val
list2.next = merge(list1, list2.next) otherwise
Namely, the smaller of the two lists' heads plus the result of a merge
on the rest of the elements.
Complexity Analysis
Time complexity : O(n + m)
Space complexity : O(n + m)
The first call to mergeTwoLists
does not return until the ends of both l1
and l2
have been reached, so n + m stack frames consume O(n + m)space.
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
} else if (l2 == null) {
return l1;
} else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}