Published: Sep 22, 2022
This is a basic linked list problem. When it is a linked list, we should always consider adding a dummy node at the head. This makes easy to handle the given linked list’s head node.
You are given the heads of two sorted linked lists
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.
- The number of nodes in both lists is in the range
-100 <= Node.val <= 100
list2are sorted in non-decreasing order.
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 =  Output: 
Create a dummy node first since we don’t know which one will come first. Also, use a current pointer to go forward. While both list1 and list2 have nodes, add one of those with grater value to current’s next. If one of list1 or list2 comes to end, add entire rest to current’s next. In the end, return dummy node’s next which points the head of list1 or list2.
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class MergeTwoSortedLists: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: dummy = ListNode() cur = dummy while list1 and list2: if list1.val <= list2.val: cur.next = list1 list1 = list1.next else: cur.next = list2 list2 = list2.next cur = cur.next cur.next = list1 or list2 return dummy.next
O(m + n)– m,n: length of list1, list2 respectively