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