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.

Return the head of the merged linked list.

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