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

class Solution {
public:

    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        // write code here
        if(pHead1==nullptr) // 若有任意一个为空 则返回另一个
            return pHead2;
        if(pHead2==nullptr)
            return pHead1;
	  // 两个指针p1,p2来进行遍历
	  // 注意 我们是将p2链入到p1中去，所以需要一个pre1指针，用来存储p1的前驱
        ListNode* p1=pHead1,*p2=pHead2;
        ListNode* pre1=nullptr;
        while(p1!=nullptr && p2!=nullptr)
        {
            if(p1->val <= p2->val)  // 只要1<2，则p1，pre1继续往后走即可
            {
                pre1=p1;
                p1=p1->next;
            }
            else // 需要将p2插入到p1的前面，即pre1的后面
            {
                ListNode* t = p2->next;
                if(pre1!=nullptr) // 如果pre1不为空
                {
                    p2->next=pre1->next;
                    pre1->next=p2;
                    pre1=pre1->next;
                }
                else // pre1为空，则特殊处理一下
                {
                    p2->next=p1; // 直接让p2的next指向p1
                    pre1=p2; // 更新pre1
                    pHead1=pre1; // 更新pHead1 
                }
                p2=t;
            }
        }
        if(p2!=nullptr) // 2还没遍历完，
            pre1->next=p2;
        return pHead1;
    }
};