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

合并两个排序的链表：最直观的想法是，双指针，pHead1指向指针1，pHead2指向指针2，使用head表示空头结点，使用tail表示尾部结点，tail初始为head，当pHead1以及pHead2均不为空时，分为三种情况，第一种是pHead1的值小于pHead2的值，那么将pHead1加入tail后面，第二种是pHead1的值大于pHead2的值，那么将pHead2加入tail后面，第三种是pHead1的值等于pHead2的值，那么将两者即pHead1和pHead2均加入tail后面。最后当其中一方为空时，将另一方不为空的依次加入tail后面即可，最后返回head->next即为链表的头结点。（链表的题其实比较偏模拟题，遇到链表题直接动手模拟一遍即可，就像下面的代码可能有些冗余，但是逻辑是非常清晰的）

ListNode* Merge(ListNode* pHead1, ListNode* pHead2) 
{
    ListNode *head=new ListNode(0); //头结点
	ListNode *tail=head; //尾部结点
	while(pHead1&&pHead2) //两个结点均不为空
	{
		if(pHead1->val<pHead2->val) //链表1小于链表2
		{
			tail->next=pHead1;
			pHead1=pHead1->next;
			tail=tail->next;
		}
		else if(pHead1->val>pHead2->val) //链表1大于链表2
		{
			tail->next=pHead2;
			pHead2=pHead2->next;
			tail=tail->next;
		}
		else //两者相等
		{
			tail->next=pHead1;
			pHead1=pHead1->next;
			tail=tail->next;
			tail->next=pHead2;
			pHead2=pHead2->next;
			tail=tail->next;
		}
	}
	while(pHead1) //pHead1还没结束
	{
		tail->next=pHead1;
		pHead1=pHead1->next;
		tail=tail->next;
	}
	while(pHead2) //pHead2还没结束
	{
		tail->next=pHead2;
		pHead2=pHead2->next;
		tail=tail->next;
	}
	return head->next;
}