# 21. Merge Two Sorted Lists

## Problem:

Merge two sorted linked lists.

```
Input: list1 = [1,2,4], list2 = [1,3,4] 
Output: [1,1,2,3,4,4]
```

<https://leetcode.com/problems/merge-two-sorted-lists/>

## What to learn:

### Precedence of Python Operators <a href="#precedence" id="precedence"></a>

| Operators                                                        | Meaning                                           |
| ---------------------------------------------------------------- | ------------------------------------------------- |
| `()`                                                             | Parentheses                                       |
| `**`                                                             | Exponent                                          |
| `+x`, `-x`, `~x`                                                 | Unary plus, Unary minus, Bitwise NOT              |
| `*`, `/`, `//`, `%`                                              | Multiplication, Division, Floor division, Modulus |
| `+`, `-`                                                         | Addition, Subtraction                             |
| `<<`, `>>`                                                       | Bitwise shift operators                           |
| `&`                                                              | Bitwise AND                                       |
| `^`                                                              | Bitwise XOR                                       |
| `\|`                                                             | Bitwise OR                                        |
| `==`, `!=`, `>`, `>=`, `<`, `<=`, `is`, `is not`, `in`, `not in` | Comparisons, Identity, Membership operators       |
| `not`                                                            | Logical NOT                                       |
| `and`                                                            | Logical AND                                       |
| `or`                                                             | Logical OR                                        |
| `lambda`                                                         | Lambda function                                   |

## Solution:

<pre class="language-python"><code class="lang-python"># 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]:
        node = ListNode()
        head = node

        while list1 and list2 :
            if list1.val &#x3C;= list2.val:
                <a data-footnote-ref href="#user-content-fn-1">head.next = list1</a>
                list1 = list1.next
            else:
                head.next = list2
                list2 = list2.next
            head = head.next
            
        if list1:
            head.next = list1

        if list2:
            head.next = list2
        
        return <a data-footnote-ref href="#user-content-fn-2">node.next</a>
</code></pre>

### Recursive

First, compare the values of list1 and list2, and make the smaller value come to the left. Then, call recursively so that 'next' links to the following value.

<pre class="language-python"><code class="lang-python"># 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]:
        if (not list1) or (list2 <a data-footnote-ref href="#user-content-fn-3">and</a> list1.val > list2.val):
            list1, list2 = list2, list1
        if list1:
            list1.next = self.mergeTwoLists(list1.next, list2)
        return list1
</code></pre>

<details>

<summary>Swap two variables</summary>

When swapping numbers, it can be solved without requiring additional space by using a simple mathematical approach. Here's how you can do it in Python:

```python
def swap_numbers(a, b): # a = 9, b = 4
    a = a + b # a = 13
    b = a - b # b = 9
    a = a - b # a = 4
    return a, b
```

</details>

[^1]: The objective here is to merge two sorted linked lists into a single sorted linked list. To do this, we want to preserve the order of nodes as well as their connections. So, when the value of a node from `list1` or `list2` is chosen to be added to the merged list, we want to bring not just its value but also its connection to its subsequent nodes. That's why we use `head.next = list1` (or `list2`) instead of head`.next.val = list1.val`.

[^2]: We set `node` (at the start of the process and then start appending the merged nodes to `head.next` (`node.next`). This way, even after `head` has moved to the end, `node.next` is still referring to the start of our merged list.\
    Returning `node.next` gives us the head of the newly merged list. We don't return `head.next` because `head` is not defined in this context.<br>

[^3]: In Python, the 'and' operator has higher precedence than the 'or' operator. This means 'and' operations are performed before 'or' operations.
