21.Merge-Two-Sorted-Lists
Last updated
Was this helpful?
Last updated
Was this helpful?
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)
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.