[链表]-21. 合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

---

解析：

方法一：

构建一个新的链表，比较两个链表中元素值，把小的挂到新的链表中。由于两个链表长度可能不相同，所以当一个链表完成插入所有元素后，另一个链表直接加入新链表尾部。

C代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* h1, struct ListNode* h2) {
    if(h1==NULL&&h2==NULL) return NULL;
    if(h1==NULL) return h2;
    if(h2==NULL) return h1;
    struct ListNode* p=NULL;
    struct ListNode* h=NULL;
    struct ListNode* t=NULL;
    while(h1&&h2){
        if(h1->val<h2->val){
            p=h1;
            h1=h1->next;
        }else{
            p=h2;
            h2=h2->next;
        }
        if(!h) h=t=p;
        else t=t->next=p;   
    }
    if(!h1){
        t->next=h2;
    }else{
        t->next=h1;
    }
    return h;
}

方法二

利用递归的写法，当某个链表空了就返回另一个链表。主要还是比较链表的元素大小。当h1当前的节点值小，则把 h1->next 和 h2 调用递归函数，返回值就赋值给 h1->next 然后返回 h1。同理当 h1大的时候，对h2进行操作。

C代码

struct ListNode* mergeTwoLists(struct ListNode* h1, struct ListNode* h2) {
    if(!h1) return h2;
    if(!h2) return h1;
    if(h1->val < h2->val){
        h1->next=mergeTwoLists(h1->next,h2);
        return h1;
    }else{
        h2->next=mergeTwoLists(h1,h2->next);
        return h2;
    }
}