# 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.

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]

# Solution

# 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]:
# Some caveats:
# One list may be longer than the other, in this case we just want to append that list onto our main list
# we should a new empty list of ListNode, and return from the second node
# for every node we determine which one is lower
# if its lower, we put it first
# we also need to be careful in case we have something likeL:
# [1, 2] [5] -> 1, 2 should go first and then 5
# so we need to not increment unless its lower
SortedList = ListNode()
# When we return, we want to return from the start of the list not the end. As we append to SortedList, we move up the list
# while we have _some_ nodes
# if either list has ended
else:
# else both nodes have head
return headOfSortedList.next