前往此题

双指针

因为两个数组都是有序的，利用有序的特性我们只要创建双指针对两个数组进行遍历并且逐个进行比较，将较小的一个放入新数组, 最后将新数组res赋值到nums1中即可。

ps: m, n代表数组中的元素数目，并不等于数组长度，如果遇到指针p1 == m 或者p2 == n时，不代表该数组已经遍历到底了。

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        res = []
        p1, p2 = 0, 0

        while p1 < m or p2 < n:
            if p1 == m:
                res.append(nums2[p2])
                p2 += 1
            elif p2 == n:
                res.append(nums1[p1])
                p1 += 1
            elif nums1[p1] < nums2[p2]:
                res.append(nums1[p1])
                p1 += 1
            else:
                res.append(nums2[p2])
                p2 += 1
        nums1[:] = res

逆向双指针

观察可知，nums1的后半部分是空的，m所对应的并不是nums1的末尾，且m + n = len(nums1)。所以我们可以通过后插的方式直接在nums上修改并且不会造成覆盖原先的数据。

算法过程

1. 创建三个指针p1,p2,tail
2. p1指nums1中的有效数字最大索引，p2指nums2中的最大索引，tail指nums1的长度len(nums) - 1或指m + n - 1
3. 遍历两个数组，将较小的一方放到nums1[tail]即可

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        p1, p2 = m - 1, n - 1
        tail = len(nums1) - 1

        while p1 >= 0 or p2 >= 0:
            if p1 == -1:
                nums1[tail] = nums2[p2]
                p2 -= 1
            elif p2 == -1:
                nums1[tail] = nums1[p1]
                p1 -= 1
            elif nums1[p1] > nums2[p2]:
                nums1[tail] = nums1[p1]
                p1 -= 1
            else:
                nums1[tail] = nums2[p2]
                p2 -= 1
            tail -= 1