Problem Description
Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.
Example 1:
Input: l1 = [1,2,4], l2 = [1,3,4] Output: [1,1,2,3,4,4]
Example 2:
Input: l1 = [], l2 = [] Output: []
Example 3:
Input: l1 = [], l2 = [0] Output: [0]
Constraints:
- The number of nodes in both lists is in the range
[0, 50]. -100 <= Node.val <= 100- Both
l1andl2are sorted in non-decreasing order.
Description taken from https://leetcode.com/problems/merge-two-sorted-lists/.
Problem Solution
#O(min(N,M)) Time, O(1) Spaceclass Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: dummy = ListNode(0) merge = dummy while l1 is not None and l2 is not None: if l1.val <= l2.val: merge.next = l1 l1 = l1.next else: merge.next = l2 l2 = l2.next merge = merge.next merge.next = l1 if l1 is not None else l2 return dummy.nextProblem Explanation
To solve this we'll want to make a third list and place the nodes onto it like Lego blocks.
We will first set a dummy head as a placeholder. We do this so that we don't have to handle any logic for placing an appropriate sorted head from one of the two lists prior to our traversal.
dummy = ListNode(0)
Afterwards, we will set the pointer for the merged list at the dummy head.
merge = dummy
We will then iterate through both lists while neither one of them is null and see if the current node value in the first list is less than or equal to the current node value in the second list.
while l1 is not None and l2 is not None: if l1.val <= l2.val:If it is, we grab the first list's node and put it on the merged list, then move the first list's pointer forward.
merge.next = l1 l1 = l1.nextIf it is not, we grab the second list's node and put it on the merged list instead, then move the second list's pointer forward.
else: merge.next = l2 l2 = l2.next After the merged list has had a node put on it from one of the two lists, we will move the merged list's pointer forward.
merge = merge.next
Once we are out of the while loop, it means one of the lists are at a null node.
We can then glue whichever list's nodes that are not null onto merged list, because they are already sorted.
merge.next = l1 if l1 is not None else l2
Once we are done, we can return all the values after our dummy head.
This will be the actual head of our output list followed by the merged sorted values.
return dummy.next
For time complexity, we'll need to traverse the smaller of the two lists because we glue the remainder of the bigger list onto the smaller list once we reach a null value, so the time complexity is O(min(M,N)).
For space complexity, we are making an entirely new list but we're reusing values from the other two lists and the question is requiring us to make the list, so we're using constant additional space.