class ListNode:
  def __init__(self, val, next=None):
    if isinstance(val,int):
      self.val = val
      self.next = next
    elif isinstance(val,list):
      self.val = val[0]
      self.next = None
      head = self
      for i in range(1,len(val)):
        node = ListNode(val[i],None)
        head.next = node
        head = head.next

class Solution:
  def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
    #如果鏈表l1為None直接返回鏈表l2即可
    if l1 is None:
      return l2
    #如果鏈表l2為None直接返回鏈表l1即可
    elif l2 is None:
      return l1
    #如果鏈表l1大于鏈表l2
    elif l1.val > l2.val:
      #更改鏈表l2下一個(gè)節(jié)點(diǎn)的指向
      l2.next = self.mergeTwoLists(l1,l2.next)
      return l2
    else:
      #更改鏈表l1下一個(gè)節(jié)點(diǎn)的指向
      l1.next = self.mergeTwoLists(l1.next,l2)
      return l1


l1 = ListNode([1,2,4])
l2 = ListNode([1,3,4])
s = Solution()
l = s.mergeTwoLists(l1,l2)
while l:
  print(l.val)
  l = l.next

class Solution:
  def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
    #用來(lái)合并鏈表
    prehead = ListNode(-1)
    #創(chuàng)建一個(gè)哨兵節(jié)點(diǎn)
    pre = prehead
    while l1 and l2:
      if l1.val > l2.val:
        pre.next = l2
        l2 = l2.next
      else:
        pre.next = l1
        l1 = l1.next
      #更改哨兵節(jié)點(diǎn)的下一個(gè)指向
      pre = pre.next
    pre.next = l1 if l1 else l2

    return prehead.next


l1 = ListNode([1,2,4])
l2 = ListNode([1,3,4])
s = Solution()
l = s.mergeTwoLists(l1,l2)
while l:
  print(l.val)
  l = l.next