Leetcode Day 6: Merge Two Sorted Lists Explained
Tags: python, leetcode, beginners, codenewbie
Published: 2024-07-07 00:35:13

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.


![Image representation of how two merged sorted linked lists looks](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4hxbclvs3gyb0zfbtal7.jpg)

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