You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
Mergenums1 and nums2 into a single array sorted in non-decreasing order.
The final sorted array should not be returned by the function, but instead be stored inside the arraynums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.
給定兩個整數陣列 nums1 和 nums2,都按照非遞減順序排列,以及兩個整數 m 和 n,分別代表 nums1 和 nums2 中元素的個數。 請將 nums1 和 nums2合併為一個按非遞減順序排列的陣列。 最終的排序陣列不應該由函數返回,而是要儲存在陣列 nums1 內部。為了實現這一點,nums1 的長度為 m + n,其中前 m 個元素表示應該合併的元素,後 n 個元素設為 0 並且應該被忽略。nums2 的長度為 n。
我一開始想法,會需要 2 迴圈去比較,然後組出一個新的 list node,最後再將新的 list node 回傳。 但是這樣的話,時間複雜度會是 O(n^2),因為每次都要從頭開始比較。 後來想說,因為兩個 list 都是已排序好的,所以可以用雙指標的方式,一次比較兩個 list 的頭節點,將較小的節點加入新的 list node,然後將該指標往後移動一位,這樣時間複雜度就會是 O(n),因為每個節點只會被比較一次。