21 合并两个升序链表
解法一:递归
假设有链表s1和s2,如果A < a,则本次比较得到链表的下一个元素为A,并且下一次B和a比较;否则,本次比较得到链表的下一个元素为a,下一次A和b比较
/**
* 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;
if(!list2)
return list1;
if(list1->val < list2->val){
list1->next = mergeTwoLists(list1->next, list2);
return list1;
}
else{
list2->next = mergeTwoLists(list1, list2->next);
return list2;
}
}
};
时间复杂度:O(n+m),其中 n 和 m 分别为两个链表的长度。因为每次调用递归都会去掉 l1 或者 l2 的头节点(直到至少有一个链表为空),函数 mergeTwoList 至多只会递归调用每个节点一次。因此,时间复杂度取决于合并后的链表长度,即 O(n+m)。
空间复杂度:O(n+m),其中 n 和 m 分别为两个链表的长度。递归调用 mergeTwoLists 函数时需要消耗栈空间,栈空间的大小取决于递归调用的深度。结束递归调用时 mergeTwoLists 函数最多调用 n+m 次,因此空间复杂度为 O(n+m)。
解法二:迭代
/**
* 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) {
ListNode* dummyNode = new ListNode(-1);
ListNode* p = dummyNode;
ListNode* p1 = list1, *p2 = list2;
while(p1 != nullptr && p2 != nullptr){
if(p1->val <= p2->val){
p->next = p1;
p1 = p1->next;
}
else{
p->next = p2;
p2 = p2->next;
}
p = p->next;
}
if(p1 != nullptr)
p->next = p1;
else
p->next = p2;
return dummyNode->next;
}
};
时间复杂度:O(n+m),其中 n 和 m 分别为两个链表的长度。因为每次循环迭代中,l1 和 l2 只有一个元素会被放进合并链表中, 因此 while 循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的,因此总的时间复杂度为 O(n+m)。
空间复杂度:O(1)。我们只需要常数的空间存放若干变量。