21. Merge Two Sorted Lists

Solution

class Solution(object):
    def mergeTwoLists(self, list1, list2):
        # Create a dummy node and a current pointer for the merged list
        dummy = ListNode(0)
        current = dummy

        # Traverse both input lists
        while list1 is not None and list2 is not None:
            if list1.val <= list2.val:
                current.next = list1  # Connect to list1
                list1 = list1.next  # Move to the next node in list1
            else:
                current.next = list2  # Connect to list2
                list2 = list2.next  # Move to the next node in list2
            current = current.next  # Move the current pointer in the merged list

        # If there are remaining nodes in list1 or list2, connect them to the merged list
        if list1 is  not None:
            current.next = list1
        if list2 is not None:
            current.next = list2

        return dummy.next  # Return the merged list starting from the next node of the dummy

Explanation in simple terms

Imagine you have two lists of numbers. Let's call them "list1" and "list2." Both lists are sorted, which means the numbers are in order from the smallest to the biggest.

Now, we want to combine these two lists into one big list while keeping all the numbers in order. It's like mixing two piles of toys while making sure all the toys stay in order from small to big.

Here's how we can do it step by step:

1. Get a pretend "dummy" toy box and an empty toy box. The "dummy" toy box is just there to help us get started.
2. Imagine you have two piles of toys, one from "list1" and the other from "list2."
3. Look at the first toy in each pile (the smallest ones). Pick the smaller one and put it in your empty toy box. This is like saying, "Which toy is tinier? We'll put that one in our new list."
4. Now, the next toy you pick will be from the pile you got the smaller toy from. So, if you took a toy from "list1," pick the next one from "list1." If you took a toy from "list2," pick the next one from "list2."
5. Keep doing this until you have gone through all the toys in both piles and placed them in your empty toy box. This way, you ensure that all the toys are in order from small to big.
6. Finally, your empty toy box is now filled with all the toys in the right order. That's your new, big, combined list!

In the computer code, we use something called a "linked list" to store the toys (numbers) and a "dummy" toy box to help us get started. The code checks which toy (number) is smaller, picks it, and keeps doing that until all the toys are in order. This is how we merge two sorted lists into one.