力扣刷题DAY3（链表/简单）

合并两个有序链表

合并两个有序链表

方法一：合并排序模板

class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {// 如果有一个链表为空，直接返回另一个链表if (!list1) return list2;if (!list2) return list1;// 创建一个虚拟头节点ListNode dummy(0);ListNode* tail = &dummy;// 合并两个链表while (list1 && list2) {if (list1->val <= list2->val) {tail->next = list1;list1 = list1->next;} else {tail->next = list2;list2 = list2->next;}tail = tail->next;}// 连接剩余的部分tail->next = list1 ? list1 : list2;return dummy.next;}
};

易错点：

忘记两个链表其中之一或者全为空的情况。

方法二：递归

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if (!list1)return list2;else if (!list2)return list1;else if(list1->val < list2->val){list1->next = mergeTwoLists(list1->next, list2);return list1;}else{list2->next = mergeTwoLists(list1, list2->next);return list2;}}
};

思路

        如果 l1 或者 l2 一开始就是空链表 ，那么没有任何操作需要合并，所以我们只需要返回非空链表。否则，我们要判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空，递归结束。每次都返回头节点，这样就可以保证每个递归的结果连起来。

复杂度分析

• 时间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。因为每次调用递归都会去掉 l1 或者 l2 的头节点（直到至少有一个链表为空），函数 mergeTwoList 至多只会递归调用每个节点一次。因此，时间复杂度取决于合并后的链表长度，即 O(n+m)。
• 空间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。递归调用 mergeTwoLists 函数时需要消耗栈空间，栈空间的大小取决于递归调用的深度。结束递归调用时 mergeTwoLists 函数最多调用 n+m 次，因此空间复杂度为 O(n+m)。