方法一：递归解决
对于此题自然不用多说，既然合并后也是有序链表，则是将两个链表的值依次比较，随后插入新链表中即可。老生常谈，我们先对两个链表是否为空进行判断，若为空，则返回另一个链表。若不为空，我们则需要重新去讨论。
不为空的情况下，
1、若list1中的值小于list2的值时，我们将list1的头结点放入新链表中，然后递归调用将list1中第二个值再与list2进行比较，进行递归
2、list2中的值小于list1的值时同理。
3、最后返回新链表newHead。
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* newHead;
if(list1==nullptr)
return list2;
else if(list2==nullptr)
return list1;
else{
if(list1->valval){
newHead=list1;
newHead->next=mergeTwoLists(list1->next,list2);
}
else{
newHead=list2;
newHead->next=mergeTwoLists(list2->next,list1);
}
}
return newHead;
}
}; 
但我们可以明显看出来，递归使用的时间复杂度和空间复杂度都是较高的，因为递归需要使用函数栈进行操作，所以会导致复杂度较高。
复杂度分析：
时间复杂度为O(m+n)，因为遍历了两个链表。
空间复杂度为O(m+n)，因为需要新链表来进行存储，长度为m+n。
m,n为两个链表的长度。
方法二：迭代
这个解法是根据LeetCode的题解来实现的，下面一张解析的图片也是截取LeetCode官方题解。
此处的哨兵节点我依稀记得在数据结构与算法这门课学过，但已经忘记，这个知识点需要掌握。
代码如下：
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* preHead = new ListNode(0);
ListNode* prev = preHead;
while (l1 != nullptr && l2 != nullptr) {
if (l1->val< l2->val) {
prev->next = l1;
l1 = l1->next;
} else {
prev->next = l2;
l2 = l2->next;
}
prev = prev->next;
}
// 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
prev->next = l1 == nullptr ? l2 : l1;
return preHead->next;
}
};
var mergeTwoLists = function(list1, list2) {
let head = new ListNode(null,null);
let temp = head;
while(l1 != null && l2 != null) {
if(l1.val<= l2.val) {
temp.next = l1;
temp = l1;
l1 = l1.next;
}else {
temp.next = l2;
temp = l2;
l2 = l2.next;
}
}
if(l1 != null) {
temp.next = l1;
}
if(l2 != null) {
temp.next = l2;
}
return head.next;
};js的代码也是大同小异，思路是一样的。
复杂度分析：
时间复杂度为O(m+n)，还是遍历两个链表。
空间复杂度为O(1)。因为每次存储的数据用常数级就行。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
