剑指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;
    }