題目：

我們提供的服務(wù)有：成都網(wǎng)站制作、網(wǎng)站建設(shè)、外貿(mào)網(wǎng)站建設(shè)、微信公眾號開發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認(rèn)證、稱多ssl等。為上1000+企事業(yè)單位解決了網(wǎng)站和推廣的問題。提供周到的售前咨詢和貼心的售后服務(wù)，是有科學(xué)管理、有技術(shù)的稱多網(wǎng)站制作公司

輸入兩個單調(diào)遞增的鏈表，輸出兩個鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。

思路1：讓兩個指針分別指向兩個鏈表，誰小就將當(dāng)前節(jié)點(diǎn)尾插入新鏈表中

代碼：

 /*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        if(pHead1==NULL)
        {
            return pHead2;
        }
        else if(pHead2==NULL)
        {
            return pHead1；
        }
        //兩個指針
        ListNode *newhead=NULL;
        ListNode *cur=NULL;
        ListNode *p1=pHead1;
        ListNode *p2=pHead2;
        ListNode *temp=NULL;
        //注意，如果是如下這種寫法：有一個很大的漏洞
        //看起來newhead的next是cur
        //但是當(dāng)找到第二個數(shù)的時候，cur就指向別處
        //newhead所在鏈表只有一個節(jié)點(diǎn)
        /*while(p1!=NULL&&p2!=NULL)
		{
			if(p1->_data<=p2->_data)
			{
				cur=p1;
				p1=p1->_next;

			}
			else
			{
				cur=p2;
				p2=p2->_next;
			}
			if(newhead==NULL)
			{
				newhead=cur;
			}
			cur->_next=NULL;
			cur=cur->_next;
		}*/   
        while(p1!=NULL&&p2!=NULL)
        {
            if(p1->val<=p2->val)
            {
                temp=p1;
                p1=p1->next;
                
            }
            else
            {
                temp=p2;
                p2=p2->next;
            }
            if(newhead==NULL)
            {
                newhead=temp;
                cur=newhead;
            }
            else
            {
                cur->next=temp;
                cur=cur->next;
            }
        }
        if(p1!=NULL)
        {
            cur->next=p1;
        }
        else
        {
            cur->next=p2;
        }
        return newhead;
    }
};

思路二：通過遞歸，每次找出最小的元素，加入到新的鏈表的后面

代碼：

ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        //終止條件
        if(pHead1==NULL)
        {
            return pHead2;
        }
        else if(pHead2==NULL)
        {
            return pHead1;
        }
        ListNode *newhead=NULL;
        if(pHead1->val<=pHead2->val)
        {
            newhead =pHead1;
            newhead ->next=Merge(pHead1->next,pHead2);
        }
        else
        {
            newhead =pHead2;
            newhead ->next=Merge(pHead1,pHead2->next);
        }
        return newhead;
    }