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

/*
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){
            return pHead2; 
        }
        if(!pHead2){
            return pHead1;
        }
        ListNode *p1=pHead1,*p2=pHead2,*q1,*q2;
        //下面几行代码让p1永远指向头结点值较小的链表，并在此链表上合并，最后也是返回头结点值小的链表
        bool a=(pHead1->val<pHead2->val)?1:0;
        if(a){
            p1=pHead1;p2=pHead2;
        }
        else{
            p1=pHead2;p2=pHead1;
        }
        //合并链表，因为需要用p1与p1->next的值夹比，p1所指链表循环终止条件为p1->next==NULL
        while(p1->next && p2){
            if(p1->val<=p2->val && p1->next->val>=p2->val){
                q1=p1->next;
                q2=p2;
                while(q2->next && p1->next->val>q2->next->val){//一口气插入范围内值的所有结点
                    q2=q2->next;
                }
                p1->next=p2;
                p2=q2->next;
                q2->next=q1;
                p1=q1;
            }
            else{
                p1=p1->next;
            }
        }
        if(p2){//连接剩余的链表
            p1->next=p2;
        }
        return (a==1)?pHead1:pHead2;
    }
};