将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：
l
1
=
[
1
,
2
,
4
]
,
l
2
=
[
1
,
3
,
4
]
l1 = [1,2,4], l2 = [1,3,4]
l1=[1,2,4],l2=[1,3,4]
输出：
[
1
,
1
,
2
,
3
,
4
,
4
]
[1,1,2,3,4,4]
[1,1,2,3,4,4]
示例 2：
输入：
l
1
=
[
]
,
l
2
=
[
]
l1 = [], l2 = []
l1=[],l2=[]
输出：
[
]
[]
[]
示例 3：
输入：
l
1
=
[
]
,
l
2
=
[
0
]
l1 = [], l2 = [0]
l1=[],l2=[0]
输出：
[
0
]
[0]
[0]
提示：
可以通过递归的方式，不断地取出值较小的节点，并将该较小值节点指向后续链表和另一个链表得合并链表，不断地堆栈，直到到达边界条件，即最后一个节点指向 N o n e None None。用列表得形式直观地表示如下：
{
l
i
s
t
1
[
0
]
+
m
e
r
g
e
(
l
i
s
t
1
[
1
:
]
,
l
i
s
t
2
)
l
i
s
t
1
[
0
]
<
l
i
s
t
2
[
0
]
l
i
s
t
2
[
0
]
+
m
e
r
g
e
(
l
i
s
t
1
,
l
i
s
t
2
[
1
:
]
)
o
t
h
e
r
w
i
s
e
\left.\left\{
每次进行合并时，会取出两个链表地头节点，直到至少一个链表为空，在最差情况下，调用次数为两个链表长度之和 ( m + n ) (m+n) (m+n)，即时间复杂度为 O ( m + n ) O(m+n) O(m+n)，空间复杂度为为栈深，每调用一次栈深加一，因此空间复杂度也为 O ( m + n ) O(m+n) O(m+n)。
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
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
执行用时：43 ms
消耗内存：16.43 MB
前面的方式是用递归的方式，把除了取出的头节点之外的链表的合并，归纳为一个合并函数，不断去调用直至边界条件，实现链表的合并。如果不把合并的操作定义为函数反复自调，那其实就是迭代的思路。
这里我们可以设定一个哨兵节点 p r e h e a d prehead prehead ，该节点相当于另起一条链表，但最后返回结果的时候可以不包含该哨兵节点，该链表方便我们得到合并后的结果。通过维护一个 p r e v prev prev 指针，不断地调整该指针指向两个链表中值较小的头节点，不断迭代直至某个链表指向空节点，当 p r e v prev prev 指向某链表的头节点之后，该链表的头节点需更新为下一个节点。如果最后某链表为空，另外的链表还有剩余，则将剩余部分直接接到 p r e v prev prev 指针后面。
同样的，迭代次数在最差情况下为 ( m + n ) (m+n) (m+n) 次，时间复杂度为 O ( m + n ) O(m+n) O(m+n)，但由于我们只维护一个指针，此时的空间复杂度为 O ( 1 ) O(1) O(1)。
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
prehead = ListNode(-1)
prev = prehead
while l1 and l2:
if l1.val <= l2.val:
prev.next = l1
l1 = l1.next
else:
prev.next = l2
l2 = l2.next
prev = prev.next
prev.next = l1 if l1 is not None else l2
return prehead.next
执行用时：34 ms
消耗内存：16.38 MB
题解来源：力扣官方题解