21. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

方法一：迭代

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, val=0, next=None):
  4. #         self.val = val
  5. #         self.next = next
  6. class Solution:
  7.     def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
  8.         if l1 == None:
  9.             return l2
  10.         elif l2 == None:
  11.             return l1
  13.         ans = ListNode(0)
  14.         cur = ans
  15.         while l1 != None and l2 != None:
  16.             if l1.val < l2.val:
  17.                 cur.next = l1
  18.                 l1 = l1.next
  19.             else:
  20.                 cur.next = l2
  21.                 l2 = l2.next
  22.             cur = cur.next
  24.         cur.next = l1 if l1 is not None else l2
  25.         return ans.next

方法二：递归

class Solution:
    def mergeTwoLists(self, l1, l2):
        if l1 is None:
            return l2
        elif l2 is None:
            return l1
        elif l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2