The problem is as follows:
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:
Output: [1,1,2,3,4,4]
Example 2:
Output: []
Example 3:
Output: [0]
Here is how I solved it:
Let’s go through the provided definition for a singly-linked list:
def __init__(self, val=0, next=None):
# Data stored in node val
self.val = val
# Reference to the next node
self.next = next
A singly linked list is a linear data structure where elements are connected in a sequence, and each element points to the next one using a pointer.
With that said, let’s step through the logic here.
Initialize a dummy_node that represents the starting point for the new merges sorted list.
Set it to a pointer current_node (address in RAM, aka a variable) to construct the new list. Initially, this pointer will point to the dummy node.
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy_node = ListNode()
current_node = dummy_node
Use a while loop to iterate through both lists at the same time until of them is null.
Choose the head with the smaller value of the two lists: if value of current node in list1 is less than value of node in list2, then append the list1 node to the merged list and move to next node in list1.
Else, append the list2 node to merged list and move to next node in list2.
We are still in the while loop. Move the current_node pointer to the newly added node
if list1.val < list2.val:
current_node.next = list1
list1 = list1.next
else:
current_node.next = list2
list2 = list2.next
current_node = current_node.next
After the while loop, if there are remaining nodes in list1 or list2, append them to the merged list.
Return the head of the merged list, which is the next node of the dummy node.
current_node.next = list1
else:
current_node.next = list2
return dummy_node.next
Here is the completed solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy_node = ListNode()
current_node = dummy_node
while list1 and list2:
if list1.val < list2.val:
current_node.next = list1
list1 = list1.next
else:
current_node.next = list2
list2 = list2.next
current_node = current_node.next
if list1:
current_node.next = list1
else:
current_node.next = list2
return dummy_node.next
