Merge two sorted lists in place
You get two lists of integers, nums1 and nums2, and two counts, m and n. nums1 has length m + n. Its first m items are real values, sorted from smallest to largest. Its last n items are placeholder 0s that only reserve room. nums2 holds n values, also sorted from smallest to largest.
Copy the values of nums2 into nums1 so that nums1 ends up holding all m + n values, sorted from smallest to largest. Work in place: write into nums1 itself and use only a few extra variables. A real value can also be 0, so only m tells you where the real values end.
The function returns nothing. The tests call it and then look at nums1.
nums1 = [1, 4, 6, 0, 0], m = 3, nums2 = [2, 5], n = 2Outputnums1 becomes [1, 2, 4, 5, 6]The two 0s at the end were room for the 2 and the 5.
nums1 = [5, 6, 0, 0], m = 2, nums2 = [1, 2], n = 2Outputnums1 becomes [1, 2, 5, 6]Every value of nums2 is smaller, so both values of nums1 move to the back.
nums1 = [0, 0], m = 0, nums2 = [3, 8], n = 2Outputnums1 becomes [3, 8]nums1 has no real values yet: both 0s are room.
len(nums1) == m + n and len(nums2) == n
0 ≤ m, n ≤ 104
-109 ≤ every value ≤ 109
nums1[:m] and nums2 are each sorted from smallest to largest.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.