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

示例：
输入：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* l1, struct ListNode* l2){
     if(l1==NULL)  
         return l2;
     if(l2==NULL)  
         return l1;
    struct ListNode* newNode;
    struct ListNode* tail;
    if(l1->val<l2->val){
        newNode=l1;
        l1=l1->next;
    }
else{
        newNode=l2;
        l2=l2->next;
  }
    tail=newNode;
    while(l1&&l2){
        if(l1->val<l2->val){
            tail->next=l1;
            l1=l1->next;
        }
        else{
           tail->next=l2;
            l2=l2->next;
        }
        tail=tail->next;
    }
    if(l1)
        tail->next=l1;
    else if(l2)
        tail->next=l2;
    return newNode;
}

C_递归合并

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

C++

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 != NULL && l2 != NULL) {
            ListNode *p = l1;
            ListNode *q = l2;
            ListNode *t, *h;//t为新链表的连接指针，h为新链表的头指针
            if(p->val > q->val) {
                t = q;
                h = q;
                q = q->next;
            } else {
                t = p;
                h = p;
                p = p->next;
            }
            while(p != NULL && q != NULL) {
                if(p->val > q->val) {
                    t->next = q;
                    t = t->next;
                    q = q->next;
                } else {
                    t->next = p;
                    t = t->next;
                    p = p->next;
                }
                
            }
            while(p != NULL && q == NULL) {
                t->next = p;
                p = p->next;
                t = t->next;
            }
            while(p == NULL && q != NULL) {
                t->next = q;
                q = q->next;
                t = t->next;
            }
            while(p == NULL && q == NULL) {
                return h;
            }
        }
        if(l1 == NULL && l2 != NULL) {
            return l2;
        }
        if(l1 != NULL && l2 == NULL) {
            return l1;
        }
        if(l1 == NULL && l2 == NULL) {
            return NULL;
        }
    }
};