text: """
  21. Merge Two Sorted Lists
  
  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.
  
  来源：力扣（LeetCode）
  链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
  """
  
  
  # Definition for singly-linked list.
  from typing import Optional
  
  
  class ListNode:
      def __init__(self, val=0, next=None):
          self.val = val
          self.next = next
  
      def __str__(self) -> str:
          return "{}{}".format(self.val, ", " + str(self.next) if self.next else "")
  
      def __repr__(self) -> str:
          return "ListNode[{}]".format(str(self))
  
  
  class Solution:
      def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
          head = ListNode()
          prev = head
  
          while list1 and list2:
              if list1.val < list2.val:
                  prev.next = list1
                  list1 = list1.next
              else:
                  prev.next = list2
                  list2 = list2.next
              prev = prev.next
  
          prev.next = list1 if list1 else list2
  
          return head.next
  
  
  if __name__ == "__main__":
      list1 = ListNode(1, ListNode(2, ListNode(4)))
      list2 = ListNode(1, ListNode(3, ListNode(4)))
      print("Input: list1 =", list1, "list2 =", list2)
      print("Output:", Solution().mergeTwoLists(list1, list2))
      list1 = None
      list2 = None
      print("Input: list1 =", list1, "list2 =", list2)
      print("Output:", Solution().mergeTwoLists(list1, list2))
  