合并两个有序链表

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

示例：

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

解法1（递归）：

思路： 初始化一个头节点head，两个链表的第一个节点比较，取较小的节点连接在head上，使用递归的方法使除去该节点的两个链表重复上述步骤，直至一个链表结束（或同时结束），最后返回head头节点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode* head;

    if(l1==NULL){
        return l2;
    }else if(l2==NULL){
        return l1;
    }
    
    if(l1->val<l2->val){
        head=l1;
        head->next=mergeTwoLists(l1->next,l2);
    }else{
        head=l2;
        head->next=mergeTwoLists(l1,l2->next);
    }
    return head;
}

解法2：

思路： 与上面算法思路相似，只是下面算法没有使用递归。该算法需注意这句（ tail->next=l1 ? l1 : l2 ;），这句处理的是比较后，有剩余节点的链表拼接在tail后

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) 
{
    struct ListNode *head,*tail;
    if(l1==NULL)
        return l2;
    else if(l2==NULL)
        return l1;
    if(l1->val<l2->val)
    {
        head=l1;
        l1=l1->next;
    }
    else
    {
        head=l2;
        l2=l2->next;
    }
    tail=head;
    while(l1 && l2)
    {
        if(l1->val < l2->val)
        {
            tail->next=l1;
            l1=l1->next;
        }
        else
        {
            tail->next=l2;
            l2=l2->next;
        }
        tail=tail->next;
    }
    
    tail->next=l1?l1:l2;
    return head;
}