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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
  public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        auto head = new ListNode(0);
        auto cur=head;//cur指向已排序链表的尾部
        while(pHead1!=nullptr&&pHead2!=nullptr)//pHead1、pHead2指向未排序链表的头部
        {
            if(pHead1->val<=pHead2->val)//比较两个未排序链表的头部，小的那个加入已排序链表
            {
                cur->next=pHead1;//尾部接上新的节点
                pHead1=pHead1->next;//头部后移一位
                cur=cur->next;//尾部后移一位
            }
            else{
                cur->next=pHead2;
                pHead2=pHead2->next;
                cur=cur->next;
            }
        }
        if(pHead1!=nullptr)//链表1还有剩余节点未连接
        {
            cur->next=pHead1;//直接接在尾部
        }
        else if(pHead2!=nullptr)
        {
            cur->next=pHead2;
        }
        return head->next;
    }
};