Merge Two Sorted Lists
Examples
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]
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]
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted linked list and return the head of the new sorted linked list.
The new list should be made up of nodes from list1 and list2.
The number of nodes in both lists is in the range [0, 50].-100 <= Node.val <= 100Both list1 and list2 are sorted in non-decreasing order.Use a dummy head and a tail pointer. Compare the current nodes of both lists, attach the smaller one to the tail, and advance that list. When one list ends, append the remainder of the other list. This handles empty lists and preserves sorted order.
At each step, the smallest available node among the two list heads must be the next node in the merged sorted list. By repeatedly choosing the smaller head and advancing, we build a correctly ordered merged list. Appending the remaining nodes is valid because they are already sorted.
O(n + m)O(1)class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0)
tail = dummy
while list1 and list2:
if list1.val <= list2.val:
tail.next = list1
list1 = list1.next
else:
tail.next = list2
list2 = list2.next
tail = tail.next
tail.next = list1 if list1 else list2
return dummy.next