合并两个有序数组(88)合并两个有序链表(21)
88. 合并两个有序数组 - 力扣(LeetCode)
21. 合并两个有序链表 - 力扣(LeetCode)
解法(88):
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
{
for (; m > 0; --m){
for (; n > 0; --n) {
//从两个数组的尾->头开始比较
if (nums1[m - 1] <= nums2[n - 1]) {
nums1[m + n - 1] = nums2[n - 1];
}else {
nums1[m + n - 1] = nums1[m - 1];
break;
}
}
if (n == 0) {
break;
}
}
if (n > 0) {
for (int i = 0; i < n; ++i) {
nums1[i] = nums2[i];
}
}
}
};
解法(21):
/**
* 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 (list2 == nullptr) {
return list1;
}
if (list1 == nullptr) {
return list2;
}
ListNode * tmp1 = list1;
ListNode * tmp2 = list2;
//用来记录tmp1 指针的 pre 指针
ListNode * tmp1_pre = nullptr;
while (tmp1 != nullptr && tmp2 != nullptr) {
ListNode * next1_ = tmp1->next;
ListNode * tmp2_ = tmp2;
if (tmp1->val == tmp2->val) {
tmp2 = tmp2->next;
tmp1->next = tmp2_;
tmp2_->next = next1_;
}else if (tmp1->val > tmp2->val) {
tmp2 = tmp2->next;
swap(tmp1->val, tmp2_->val);
tmp1->next = tmp2_;
tmp2_->next = next1_;
}
tmp1_pre = tmp1;
tmp1 = tmp1->next;
}
if (tmp2 != nullptr) {
tmp1_pre->next = tmp2;
}
return list1;
}
};
总结:
(88)和(21)的时间复杂度都是O(m+n),空间复杂度都是O(1)。这里面有序数组为了做到空间复杂度O(1),需要从尾->头开始进行比较,而有序链表因为允许随机insert和delete,所以从头->尾开始进行比较