Linked List - Merge two sorted lists

"""
https://leetcode.com/problems/merge-two-sorted-lists/description/

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.


2024.08.21
- The way I remembered how to write the code was to start with the `if curr1.val <= curr2.val:` check. I then wrote
the stuff in the block: `current.next = curr1; curr1 = curr1.next`. And then it was clear I needed to add the `else:`
case.
- I think at this point it became clear that this was very similar to the mergesort pattern of handling the case
where you're drawing from two different lists, then needing to handle the case where one of the lists still has items
in it when the other has run out. And I remembered the explanation that I could just append the remaining node
without needing to iterate through its following nodes.
- The last thing to remember was to create a dummy head node. I'm not sure of a way to arrive at this by first
principles in an interview setting, I just had it memorized.
- I got an error on a test case because I didn't initialize the dummy head node to have an initial value.
"""

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


# Iterative solution
"""
2024.08.21
- The way I remembered how to write the code was to start with the `if curr1.val <= curr2.val:` check. I then wrote
the stuff in the block: `current.next = curr1; curr1 = curr1.next`. And then it was clear I needed to add the `else:`
case.
- I think at this point it became clear that this was very similar to the mergesort pattern of handling the case
where you're drawing from two different lists, then needing to handle the case where one of the lists still has items
in it when the other has run out. And I remembered the explanation that I could just append the remaining node
without needing to iterate through its following nodes.
- The last thing to remember was to create a dummy head node. I'm not sure of a way to arrive at this by first
principles in an interview setting, I just had it memorized.
- I got an error on a test case because I didn't initialize the dummy head node to have an initial value.
"""

class Solution:
    def mergeTwoLists(self, l1, l2):
        prehead = ListNode(-1)
        curr = prehead
        while l1 and l2:
            if l1.val <= l2.val:
                curr.next = l1
                l1 = l1.next
            else:
                curr.next = l2
                l2 = l2.next
            curr = curr.next
        curr.next = l1 if l1 else l2
        return prehead.next




# Recursive Solution
"""
I think the way to remember this one is to remember that the base case is if one of the nodes is None. Once you write out those two if conditions, it becomes clear that the recursive case is when you have two nodes and need to decide which one is going to be the head of the returned list. So you then write out the `l1.val <= l2.val` check and then the `return l1` line, and it becomes clear that the missing piece is `l1.next = ...` and you just need to fill in the `...` part.
"""
class Solution:
    def mergeTwoLists(self, l1, l2):
        # base case
        if not l1:
            return l2
        elif not l2:
            return l1

        # recursive case
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2