Merge two ascending sorted linked lists into a new sorted linked list. The new list is constructed by splicing together all nodes from the two input linked lists.

• Example 1:
  Input: l1 = [1,2,4], l2 = [1,3,4]
  Output: [1,1,2,3,4,4]
• Example 2:
  Input: l1 = [], l2 = [0]
  Output: [0]

class Solution:
    def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
        # Base cases: return the remaining list if one is fully traversed
        if not list1:
            return list2
        if not list2:
            return list1
        
        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2

class ListNode:
    def __init__(self, val=0, next_node=None):
        self.val = val
        self.next = next_node

    @classmethod
    def build_from_list(cls, values: list) -> 'ListNode':
        """Create a linked list from an input Python list"""
        current_head = None
        for val in reversed(values):
            current_head = ListNode(val, next_node=current_head)
        return current_head

    def convert_to_list(self) -> list:
        """Convert the linked list back to a native Python list"""
        output = []
        current = self
        while current is not None:
            output.append(current.val)
            current = current.next
        return output


class Solution:
    def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
        # Base cases: return remaining list if one input is empty
        if not list1:
            return list2
        if not list2:
            return list1
        
        # Recursively merge remaining nodes after picking the smaller value
        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2


if __name__ == '__main__':
    # Create input linked lists from test values
    list_a = ListNode.build_from_list([1, 2, 4])
    list_b = ListNode.build_from_list([1, 3, 4])
    
    solution = Solution()
    merged_result = solution.mergeTwoLists(list_a, list_b)
    
    print(merged_result.convert_to_list())