合并两个有序数组（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，所以从头->尾开始进行比较