leet0021. lint0006.

C语言，方法一：尤其需要注意的是前面两个return语句一定要有

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    //下面两个判断一定要有，否则while循环从未进入的话，last为NULL
    //那么最后面的last还是NULL，空指针错误
    if(l2==NULL)
        return l1;
    if(l1==NULL)
        return l2;
    struct ListNode* head=NULL;
    struct ListNode* last=NULL;
    while(l1!=NULL && l2!=NULL){
        struct ListNode* tmp=NULL;
        if(l1->val < l2->val){
            tmp = l1;
            l1 = l1->next;
        }else{
            tmp = l2;
            l2 = l2->next;
        }
        if(head==NULL){
            head= last = tmp;
        }else{
            last->next = tmp;//挂接新节点，
            last = tmp;//当前节点指向新节点
        }
    }
    if(l1!=NULL)
        last->next = l1;
    if(l2!=NULL)
        last->next = l2;
    return head;
}

C语言，方法二，新建一个dummy节点，思路和方法一其实是一样的，只是程序看上去更简单一些，同样要注意开头的两个判断不可缺少。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    if(l2==NULL)
        return l1;
    if(l1==NULL)
        return l2;
    struct ListNode* dummy=(struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* last=dummy;
    while(l1!=NULL && l2!=NULL){
        if(l1->val < l2->val){
            last->next = l1;//挂接新节点
            l1 = l1->next;
        }else{
            last->next = l2;//挂接新节点
            l2 = l2->next;
        }
        last = last->next;//更新当前节点
    }
    if(l1!=NULL)
        last->next = l1;
    if(l2!=NULL)
        last->next = l2;
    return dummy->next;
}

Java，方法三：Java版不需要前面两个判断语句，和引用有关，C没有引用这种类型。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode head = dummy;
        while(l1!=null && l2!=null){
            if(l1.val>l2.val){
                dummy.next=l2;
                l2=l2.next;
            }else{
                dummy.next=l1;
                l1=l1.next;
            }
            dummy=dummy.next;
        }
        if(l1!=null)
            dummy.next=l1;
        if(l2!=null)
            dummy.next=l2;
        return head.next;
    }
}

• lint0006 Merge Two Sorted Arrays
  这个Java程序的选择过程很提现技巧

public class Solution {
    public int[] mergeSortedArray(int[] A, int[] B) {
        if(A==null)return B;
        if(B==null)return A;
        int lenA = A.length, lenB = B.length;
        int n = lenA+lenB;
        int[] ret = new int[n];
        int i=0,j=0,k=0;
        for( ; k<n; ++k){
            //&&后面的是B的元素遍历完或者B[j]大于A[i]
            if(i<lenA && (j>=lenB || A[i]<=B[j])){
                ret[k] = A[i++];
            }else{//其他情况选择B[j]
                ret[k] = B[j++];
            }
        }
        return ret;
    }
}