Problem

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.

List 1: [1] -> [2] -> [4]

List 2: [1] -> [3] -> [4]

Output: [1] -> [1] -> [2] -> [3] -> [4] -> [4]

Given Code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:

Solution

Logic

Alright, let's break down the code step by step:

1. Initial Check:

    if list1 is None or list2 is None:
        return list1 if not list2 else list2
   

   This part checks if either list1 or list2 is empty. If one of them is empty, it returns the non-empty list. If both are empty, it doesn't matter which one is returned because they are both empty.

2. Initialization:

    newList = returnList = ListNode()
   

   Here, two variables (newList and returnList) are created and set to a new empty node. These nodes will be used to build the merged list.

3. Merging Loop:

    while list1 or list2:
   

   This loop continues as long as either list1 or list2 has elements. It iterates through the lists, comparing the values of the current nodes and adding the smaller value to the new list.

4. Value Assignment:

    value: int = 0
    if not list2 or (list1 and list1.val <= list2.val):
        value = list1.val
        list1 = list1.next
    else:
        value = list2.val
        list2 = list2.next
   

   This part determines which node's value (list1 or list2) should be added to the merged list. It compares the values and moves to the next node of the list with the smaller value.

5. Building the Merged List:

    newList.next = ListNode(value)
    newList = newList.next
   

   The code creates a new node with the determined value and adds it to the merged list. Then, it moves the newList pointer to the newly added node for the next iteration.

6. Final Result:

    return returnList.next
   

   Finally, it returns the merged list starting from the node after the initially created empty node (returnList).

In simple terms, this code takes two lists of numbers, compares their values one by one, and creates a new list with all the values in sorted order. It's like merging two lists of numbers into a single sorted list.

Code

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if list1 is None or list2 is None:
            return list1 if not list2 else list2

        newList = returnList = ListNode()
        while list1 or list2:
            value: int = 0
            if not list2 or (list1 and list1.val <= list2.val):
                value = list1.val
                list1 = list1.next
            else:
                value = list2.val
                list2 = list2.next
            newList.next = ListNode(value)
            newList = newList.next
        return returnList.next