Simona Cancian

Posted on

# Leetcode Day 6: Merge Two Sorted Lists Explained

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.

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]
``````

Here is how I solved it:
Let's go through the provided definition for a singly-linked list:

``````class ListNode:
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.
``````class Solution:
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
``````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
``````
• 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.
``````if list1:
current_node.next = list1
else:
current_node.next = list2

return dummy_node.next
``````

Here is the completed solution:

``````class 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
``````