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

难度：简单

题⽬分析：重点便是有序⼆字。有序的链表题在删除重复元素、合并等问题，都难度不⼤。

同时记得考虑特殊输⼊，两个均为空链表，⼀个为空链表的情形。

解法⼀：递归

给定链表 l1 和 l2, ⽐较第⼀个元素，如 l1 第⼀个元素⼩于 l2 第⼀个元素，那返回的列表，表头就是 l1 第⼀个元素。

少了⼀个元素的 l1 链表 和 l2 链表，此时⼜是⼀个排序问题，于是，我们可以调⽤我们正在编写（虽然还没完成，但有这个功能啊！），

返回的⼀定是个排好序的链表，接上即可，于是，求解代码如下：

# Definition for singly-linked list.

# class ListNode:

#     def __init__(self, x):

#         self.val = x

#         self.next = None

class

 Solution

:

def

mergeTwoLists

(

self

,

 l1

:

 ListNode

,

 l2

:

 ListNode

)

->

 ListNode

:

if

 l1 

is

None

:

return

 l2

if

 l2 

is

None

:

return

 l1

if

 l1

.

val