Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

递归版

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        if(l1==NULL)    return l2;
        if(l2==NULL)    return l1;
            
        ListNode *p=NULL;
        
        if(l1->val<l2->val)
        {
            p=l1;
            p->next=mergeTwoLists(l1->next,l2);
        }
        else
        {
            p=l2;
            p->next=mergeTwoLists(l1,l2->next);
        }
    }
};

循环版

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        
        ListNode *p,*q,*r,*s;
        
        if(l1==NULL)return l2;
        if(l2==NULL)return l1;
        
        if(l1->val<l2->val)
        {
            r=l1;
            p=l1->next;
            q=l2;
        }
        else
        {
            r=l2;
            p=l1;
            q=l2->next;
        }
        
        s=r;
        
        while(p!=NULL&&q!=NULL)
        {
            if(p->val<q->val)
            {
                r->next=p;r=r->next;
                p=p->next;
            }
            else
            {
                r->next=q;r=r->next;
                q=q->next;
            }
        }
        
        if(p!=NULL) r->next=p;
        if(q!=NULL) r->next=q;
        
        return s;
    }
};

leetcode-Merge Two Sorted Lists