21. Merge Two Sorted Lists — LeetCode(Python)
I got you!
Problem:
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Example 1:
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]Example 2:
Input: list1 = [], list2 = []
Output: []Example 3:
Input: list1 = [], list2 = [0]
Output: [0]Constraints:
- The number of nodes in both lists is in the range
[0, 50]. -100 <= Node.val <= 100- Both
list1andlist2are sorted in non-decreasing order.
Solution:
dummy = curr = ListNode(0)
while list1 and list2:
if list1.val < list2.val:
curr.next = list1
list1 = list1.next
else:
curr.next = list2
list2 = list2.next
curr = curr.next
curr.next = list1 or list2
return dummy.nextExplanation:
Here, we use a two-pointer approach. We use variables list1 and list2 as two pointers to the two list heads.
Then we merge the two lists starting from a dummy node. This dummy node will be useful later.
We traverse the two lists simultaneously and we keep linking the smaller valued ListNode to our dummy node using pointers.
After the while loop is terminated, which means either list1 or list 2 have been traversed, we point to the remaining untraversed list.
We then use the dummy node we had created and return the next node which would contain our desired merged linked list traversal.
Time and Space Complexity:
We are traversing each list once which would take linear time and we are using only a dummy node which counts as constant space.
Thus, if n is the length of list1 and list2 combined,
Time Complexity: O(n)
Space Complexity: O(1)
