Link:: https://leetcode.com/problems/merge-two-sorted-lists/
up:: [[Leetcode MOC]]
# Merge Two Sorted Lists
## Problem
You are given the heads of two sorted linked lists `list1` and `list2`.
Merge the two lists in a 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]`
### Constraints
- The number of nodes in both lists is in the range `[0, 50]`.
- `-100 <= Node.val <= 100`
- Both `list1` and `list2` are sorted in **non-decreasing** order.
## Solution
### Mine
#### Python
```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:
return list2
if not list2:
return list1
dummy = ListNode()
tail = dummy
while list1 and list2:
if list1.val <= list2.val:
tail.next = list1
list1 = list1.next
else:
tail.next = list2
list2 = list2.next
tail = tail.next
if list1:
tail.next = list1
elif list2:
tail.next = list2
return dummy.next
```
#### Rust
### LC's
## Things I Learned
## Scratchpad
Nested loop through lists? based on which is greater, update next of first? But that would mutate the list.