合并两个排序的链表

• 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
• Java 代码（递归）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        if(l1.val < l2.val){
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }else{
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

• C++ 代码

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        ListNode *p,*q,*head,*pre=NULL;
        p=pHead1;
        q=pHead2;
        if(p&&!q) return p;
        if(!p&&q) return q;
        if(p&&q)
        {
             if(q->val>=p->val) 
             {
                 head=p;
                 pre=p;
                 p=p->next;
             }
            else 
            {
                head=q;
                pre=q;
                q=q->next;
                pre->next=p;
            }
        }
        
       while(p&&q)
       {
           if(q->val<p->val) 
           {
               pre->next=q;
               pre=q;
               q=q->next;
               pre->next=p;
           }
           else 
           {
               pre=p;
               p=p->next;
           }
       }
        if(q) pre->next=q;
        return head;
        
    }
};