21. Merge Two Sorted Lists
## description
## 21. Merge Two Sorted Lists
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into 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:
1Input: list1 = [1,2,4], list2 = [1,3,4]
2Output: [1,1,2,3,4,4]Example 2:
1Input: list1 = [], list2 = []
2Output: []Example 3:
1Input: list1 = [], list2 = [0]
2Output: [0]- –The number of nodes in both lists is in the range [0, 50].
- –-100 <= Node.val <= 100
- –Both list1 and list2 are sorted in non-decreasing order.
Constraints:
## notes
### Intuition
Since both lists are sorted, we can build the merged list by always taking the smaller of the two current nodes. This is similar to the merge step in merge sort.
### Implementation
Create a dummy node to simplify head handling and a curr pointer for building the result. While both lists have nodes, compare their values—append the smaller one to the result and advance that list's pointer. After the main loop, one list may have remaining nodes; append them directly since they're already sorted.
### Edge-cases
If either list is initially empty, the other list is returned as-is. The dummy node eliminates special case handling for the first element.
- –Time: O(m + n) — each node visited once
- –Space: O(1) — reusing existing nodes (or O(m + n) if creating new nodes)
### Complexity
## solution
1from typing import Optional
2from lcutils import ListNode
3
4# Definition for singly-linked list.
5# class ListNode:
6# def __init__(self, val=0, next=None):
7# self.val = val
8# self.next = next
9class Solution:
10 def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
11 l1, l2 = list1, list2
12 dummy = ListNode()
13 curr = dummy
14 while l1 and l2:
15 if l1.val < l2.val:
16 curr.next = ListNode(l1.val)
17 l1 = l1.next
18 else:
19 curr.next = ListNode(l2.val)
20 l2 = l2.next
21 curr = curr.next
22
23 while l1:
24 curr.next = ListNode(l1.val)
25 curr = curr.next
26 l1 = l1.next
27
28 while l2:
29 curr.next = ListNode(l2.val)
30 curr = curr.next
31 l2 = l2.next
32
33 return dummy.next
34
35
36
37
38if __name__ == "__main__":
39 # Include one-off tests here or debugging logic that can be run by running this file
40 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
41 solution = Solution()
42