迭代

同时遍历两个链表 ， 当前结点值较小的结点插入新的链表尾部。直到有一个链表为空 ， 我们将另一个非空链表插入新的链表尾部。

提示 : 使用哑结点，避免特判头结点。二路归并思想应用于链表~

class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {auto dummy = new ListNode (-1);auto tail = dummy;while(list1&&list2){if(list1->valval){tail->next = list1;tail = tail->next;list1 = list1->next;} else{tail = tail->next = list2;list2 = list2->next;}}if(list1) tail->next = list1;if(list2) tail ->next = list2;return dummy->next;}
};

时间复杂度 O(n+m)O(n+m)O(n+m) ， nnn 是链表 list1list1list1 的长度 ， mmm 是链表 list2list2list2 的长度 ， 遍历两个链表的时间复杂度 O(n)O(n)O(n) 。

空间复杂度 O(1)O(1)O(1) ， 除若干变量使用的常量级空间，没有使用额外的线性空间(算上答案空间，和递归的空间复杂度 O(n+m)O(n+m)O(n+m) 一样)。

递归

巧妙的递归实现 ， 保留较小结点 ， 递归较大结点。

class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if(!list1) return list2;//终止条件if(!list2) return list1;if(list1->valval){//保留较小结点,递归较大结点list1->next = mergeTwoLists(list1->next,list2);return list1;}else{list2->next = mergeTwoLists(list1,list2->next);return list2;}}
};

时间复杂度 O(n+m)O(n+m)O(n+m) ， nnn 是链表 list1list1list1 的长度 ， mmm 是链表 list2list2list2 的长度 ， 递归遍历两个链表的时间复杂度 O(n)O(n)O(n) 。

空间复杂度 O(n+m)O(n+m)O(n+m) ， 递归体压栈的最大深度 O(n)O(n)O(n) ， 空间复杂度 O(n)O(n)O(n) 。

博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

AC