题解 | #合并两个排序的链表#

/*
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;
		if(pHead2 == NULL)
		    return pHead1;
        ListNode *p1,*p2,*tail;
		p1 = pHead1;
		p2 = pHead2;
		//将pHead作为新链表的头结点
		if(pHead1->val>pHead2->val)
		{
			pHead1 = pHead2;
			p2 = p2->next;
		}
		else
		{
			p1 = p1->next;
		}
		tail = pHead1;
		ListNode * temp;
		while(p1&&p2)
		{
			if(p1->val>p2->val)
			{
				temp = p2->next;
				tail->next = p2;
				tail = p2;
				p2 = temp;
			}
			else
			{
				temp = p1->next;
				tail->next = p1;
				tail = p1;
				p1 = temp;
			}
		}
		if(p1) 
		{
			tail->next = p1;
		}
		if(p2)
		{
			tail->next = p2;
		}
		return pHead1;
    }
};