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

示例：

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

解法一：双指针法

  1. class Solution:
  2.     def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
  3.         sentinel = p = ListNode()
  4.         while l1 and l2:
  5.             if l1.val < l2.val:
  6.                 p.next = l1
  7.                 l1 = l1.next
  8.             else:
  9.                 p.next = l2
  10.                 l2 = l2.next
  11.             p = p.next
  12.         p.next = l1 or l2
  13.         return sentinel.next

解法二：递归法

递归法很容易得到退出条件：当l1与l2都耗尽时，返回None，即合并后的链表尾部。当l1为空或l2为空时，返回不为空的链表即可。
子问题是比较l1与l2当前节点的值，如果l1的值小于l2的值，则l1当前节点为合并后的链表头，同时尝试将l1.next与l2进行合并。子问题应返回链表头节点。

  1. class Solution:
  2.     def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
  3.         if not l1 and not l2:
  4.             return None
  5.         if not l1 or not l2:
  6.             return l1 or l2
  7.         if l1.val < l2.val:
  8.             l1.next = self.mergeTwoLists(l1.next, l2)
  9.             return l1
  10.         else:
  11.             l2.next = self.mergeTwoLists(l1, l2.next)
  12.             return l2