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

/*
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*head,*tail;//用于返回的链表
        ListNode*p,*q;//用于进行比较的两个指针
        //首先摘取一个节点作为头节点
        if(pHead1->val<pHead2->val){
            head=pHead1;tail=pHead1;
            pHead1=pHead1->next;
            tail->next=NULL;
        }
        else{
            head=pHead2;tail=pHead2;
            pHead2=pHead2->next;
            tail->next=NULL;
        }
        
        //开始逐个比较，将小的节点插入
        p=pHead1;q=pHead2;
        pHead1=pHead1->next;
        pHead2=pHead2->next;
        while(p!=NULL&&q!=NULL){
            if(p->val<q->val){
                tail->next=p;
                tail=p;
                tail->next=NULL;
                p=pHead1;if(pHead1!=NULL)pHead1=pHead1->next;
            }
            else{
                tail->next=q;
                tail=q;
                tail->next=NULL;
                q=pHead2;if(pHead2!=NULL)pHead2=pHead2->next;
            }
        }
        
        //将多的链表插入head链表中
        if(p==NULL)tail->next=q;
        if(q==NULL)tail->next=p;
        return head;
    }
};