# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
"""
Approach 2: Iteration

Intuition

We can achieve the same idea via iteration by assuming that l1 is entirely
less than l2 and processing the elements one-by-one, inserting elements of
l2 in the necessary places in l1.

Algorithm

First, we set up a false "prehead" node that allows us to easily return the
head of the merged list later. We also maintain a prev pointer, which
points to the current node for which we are considering adjusting its next
pointer. Then, we do the following until at least one of l1 and l2 points
to null: if the value at l1 is less than or equal to the value at l2,
then we connect l1 to the previous node and increment l1. Otherwise, we
do the same, but for l2. Then, regardless of which list we connected, we
increment prev to keep it one step behind one of our list heads.

After the loop terminates, at most one of l1 and l2 is non-null.
Therefore (because the input lists were in sorted order), if either list is
non-null, it contains only elements greater than all of the
previously-merged elements. This means that we can simply connect the
non-null list to the merged list and return it.

"""

To see this in action on an example, check out the animation below:

class Solution:
    def mergeTwoLists(self, first: Optional[ListNode], second: Optional[ListNode]) -> Optional[ListNode]:

        dummy = ListNode(-101)
        temp = dummy

        while(first and second):
            if first.val <= second.val:
                dummy.next = first
                first = first.next
            else:
                dummy.next = second
                second = second.next
            dummy = dummy.next

        if not first:
            dummy.next = second

        if not second:
            dummy.next = first

        return temp.next