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

/*
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==nullptr&&pHead2==nullptr){
			return nullptr;
		}
		if(pHead1==nullptr&&pHead2!=nullptr){
			return pHead2;
		}
		if(pHead1!=nullptr&&pHead2==nullptr){
			return pHead1;
		}
		ListNode *p1=pHead1->next;
        ListNode *p2=pHead2->next;
		ListNode *ans;
		if(pHead1->val>pHead2->val){
			ans=pHead2;
			while(pHead1->val>p2->val){
				pHead2=pHead2->next;
				p2=pHead2->next;
				if(p2==nullptr){
					pHead2->next=pHead1;
					return ans;
				}
			}
			pHead2->next=pHead1;
			pHead2=p2;
			p2=p2->next;
		}
		else{
			ans=pHead1;
		}
		while(pHead1!=nullptr&&pHead2!=nullptr){
			if(p1==nullptr){
				break;
			}
			if(p1->val>pHead2->val){
				pHead1->next=pHead2;
				pHead2->next=p1;
				pHead1=pHead2;
				pHead2=p2;
				if(p2!=nullptr){
					
					p2=p2->next;
				}		
			}
			else{
				if(p1!=nullptr){
					p1=p1->next;
				}
				else{
					p1=pHead1;
				}
				pHead1=pHead1->next;
			}
		}
		if(p1==nullptr){
			pHead1->next=pHead2;
		}
		return ans;
    }
};