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

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode* p=pHead1,*q=pHead2;
		//创建一个虚拟头结点
		ListNode* Head=new ListNode(0);
		Head->next=NULL;
		//创建尾指针尾插
		ListNode* tail=Head;
		while(p&&q)
		{
			ListNode* t=NULL;//临时存储p/q的后继
			if(p->val<=q->val)
			{
				t=p->next;
				p->next=tail->next;
				tail->next=p;
				tail=p;
				p=t;
			}
			else {
				t=q->next;
				q->next=tail->next;
				tail->next=q;
				tail=q;
				q=t;
			}
		}
		//处理还有剩余的
		if(q)  p=q;
		tail->next=p; 
		return Head->next;
    }
};