题目：
Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.
题解：
这道题是说让B merge到 A 里面。
先复习下原本我们在MergeSort里面怎么利用一个新建的数量来merge two array：
代码如下：
1 public int[] mergeTwoList(int[] A, int[] B) {
2 int[] C = new int[A.length + B.length];
3 int k = 0;
4 int i = 0;
5 int j = 0;
6 while(i < A.length && j < B.length) {
7 if (A[i] < B[j])
8 C[k++] = A[i++];
9 else
10 C[k++] = B[j++];
11 }
12 while (i < A.length)
13 C[k++] = A[i++];
14 while (j < B.length)
15 C[k++] = B[j++];
16 return C;
17 }
2 int[] C = new int[A.length + B.length];
3 int k = 0;
4 int i = 0;
5 int j = 0;
6 while(i < A.length && j < B.length) {
7 if (A[i] < B[j])
8 C[k++] = A[i++];
9 else
10 C[k++] = B[j++];
11 }
12 while (i < A.length)
13 C[k++] = A[i++];
14 while (j < B.length)
15 C[k++] = B[j++];
16 return C;
17 }
然后我们再顺便复习下，怎么merge two linked list，代码如下：
1 public ListNode mergeTwoLists(ListNode leftlist, ListNode rightlist){
2 if(rightlist == null)
3 return leftlist;
4 if(leftlist == null)
5 return rightlist;
6
7 ListNode fakehead = new ListNode(-1);
8 ListNode ptr = fakehead;
9 while(rightlist!=null&&leftlist!=null){
10 if(rightlist.val<leftlist.val){
11 ptr.next = rightlist;
12 ptr = ptr.next;
13 rightlist = rightlist.next;
14 }else{
15 ptr.next = leftlist;
16 ptr = ptr.next;
17 leftlist = leftlist.next;
18 }
19 }
20
21 if(rightlist!=null)
22 ptr.next = rightlist;
23 if(leftlist!=null)
24 ptr.next = leftlist;
25
26 return fakehead.next;
27 }
2 if(rightlist == null)
3 return leftlist;
4 if(leftlist == null)
5 return rightlist;
6
7 ListNode fakehead = new ListNode(-1);
8 ListNode ptr = fakehead;
9 while(rightlist!=null&&leftlist!=null){
10 if(rightlist.val<leftlist.val){
11 ptr.next = rightlist;
12 ptr = ptr.next;
13 rightlist = rightlist.next;
14 }else{
15 ptr.next = leftlist;
16 ptr = ptr.next;
17 leftlist = leftlist.next;
18 }
19 }
20
21 if(rightlist!=null)
22 ptr.next = rightlist;
23 if(leftlist!=null)
24 ptr.next = leftlist;
25
26 return fakehead.next;
27 }
可以看出merge的思路都是在从头比较两个list的value，用两个指针分别指向当前要比较的node上面。而且最后都会处理下剩下的元素。
而这道题是不能借助一个新的array的，那么我们就不好从前往后比了（不好插入位置）。方便的方法是从后往前比，然后最后处理剩下的元素。
代码如下：
public void merge(int A[], int m, int B[], int n) {
while(m > 0 && n > 0){
if(A[m-1] > B[n-1]){
A[m+n-1] = A[m-1];
m--;
}else{
A[m+n-1] = B[n-1];
n--;
}
}
while(n > 0){
A[m+n-1] = B[n-1];
n--;
}
}
while(m > 0 && n > 0){
if(A[m-1] > B[n-1]){
A[m+n-1] = A[m-1];
m--;
}else{
A[m+n-1] = B[n-1];
n--;
}
}
while(n > 0){
A[m+n-1] = B[n-1];
n--;
}
}
Merge Sorted Array leetcode java（回顾MergeTwoArray和MergeTwoLinkedList）,布布扣,bubuko.com
Merge Sorted Array leetcode java（回顾MergeTwoArray和MergeTwoLinkedList）