学步园

1. 合并两个已排序的数组

public class Solution {
    /**
     *  Careercup 11.1
     *  O(m+n)
     * */
    public void merge(int A[], int m, int B[], int n) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        int ia = m-1;
        int ib = n-1;
        int iall = m+n-1;
        while(ia>=0 && ib>=0){  // 从后往前合并, 把大的先往后挪.
            if(A[ia] > B[ib]){
                A[iall] = A[ia];
                ia--;
            }else{
                A[iall] = B[ib];
                ib--;
            }
            iall--;
        }
        // 只用将B剩下的复制到A上, 若A有剩下的,则不用动.
        while(ib>=0){
            A[iall] = B[ib];
            iall--;
            ib--;
        }
    }
}

2. 合并两个排序的list

O(n)时间, O(1)空间

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        ListNode newHead = (l1.val <= l2.val)?l1:l2;
        ListNode smaller = null;
        ListNode prev = newHead;
        // compare two heads util one of them is null
        while(l1 != null & l2 != null){
            if(l1.val <= l2.val){
                smaller = l1;
                l1 = l1.next;
            }else{
                smaller = l2;
                l2 = l2.next;
            }
            prev.next = smaller;
            prev = smaller;
        }
        
        // deal with remaining list
        prev.next = (l1 == null) ? l2:l1;
        
        return newHead;
    }
}