归并排序

void merge_sort(vector<int> &nums, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        merge_sort(nums, left, mid);
        merge_sort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }
}

void merge(vector<int> &nums, int left, int mid, int right) {
    vector<int> temp;
    int i = left;
    int j = mid + 1;
    while (i <= mid && j <= right) {
        if (nums[i] > nums[j]) {
            temp.push_back(nums[j++]);
        } else
            temp.push_back(nums[i++]);
    }
    //下面两个循环只有一个会执行
    while (i <= mid)
        temp.push_back(nums[i++]);
    while (j <= right)
        temp.push_back(nums[j++]);
    for (int i = 0; i < temp.size(); i++)
        nums[left + i] = temp[i];
}

归并

21. 合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例:

输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
struct ListNode {
    int val;
    ListNode *next;

    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode *dummy = new ListNode(0);
        ListNode *cur = dummy;
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val < l2->val) {
                cur->next = l1;
                cur = cur->next;
                l1 = l1->next;
            } else {
                cur->next = l2;
                cur = cur->next;
                l2 = l2->next;
            }
        }
        if (l1 != nullptr)
            cur->next = l1;
        if (l2 != nullptr)
            cur->next = l2;
        return dummy->next;
    }

    ListNode *mergeTwoLists2(ListNode *l1, ListNode *l2) {
        if (l1 == nullptr)
            return l2;
        if (l2 == nullptr)
            return l1;
        if (l1->val < l2->val) {
            l1->next = mergeTwoLists2(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists2(l1, l2->next);
            return l2;
        }
    }
};

88. 合并两个有序数组

给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。

说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。
示例:

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

输出: [1,2,2,3,5,6]
public class Eighty_eight {
    /**
     * 倒着合并
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int index1 = m - 1;
        int index2 = n - 1;
        int indexNew = m + n - 1;
        while (index1 >= 0 || index2 >= 0) {
            if (index1 < 0) {
                nums1[indexNew--] = nums2[index2--];
            } else if (index2 < 0) {
                nums1[indexNew--] = nums1[index1--];
            } else if (nums1[index1] > nums2[index2]) {
                nums1[indexNew--] = nums1[index1--];
            } else {
                nums1[indexNew--] = nums2[index2--];
            }
        }
    }
}
class Solution {
public:
    void merge(vector<int> &nums1, int m, vector<int> &nums2, int n) {
        int new_index = m + n - 1;
        int i = m - 1;
        int j = n - 1;
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[new_index--] = nums1[i--];
            } else {
                nums1[new_index--] = nums2[j--];
            }
        }
        while (i >= 0) {
            nums1[new_index--] = nums1[i--];
        }
        while (j >= 0) {
            nums1[new_index--] = nums2[j--];
        }
    }
};

return the last

0