劍指offer之面試題17 ：合并兩個排序的鏈表

題目：

輸入兩個單調遞增的鏈表，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿足單調不減規則。

思路1：讓兩個指針分別指向兩個鏈表，誰小就將當前節點尾插入新鏈表中

代碼：

 /*
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
        //但是當找到第二個數的時候，cur就指向別處
        //newhead所在鏈表只有一個節點
        /*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;
    }