合并两个排序的链表

题目：

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围： 0 le n le 10000≤n≤1000，-1000 le 节点值 le 1000−1000≤节点值≤1000
要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

解题思路：

1. 判断链表是否为空，一个为空，直接返回另一个链表
2. 两链表不为空，比较两链表的值，值较小的插入，next依次向后移
3. 插入到最后，若一个链表已经完成，另一个链表还有数据，则直接连接在末尾

ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        //判断链表是否未空
        if(pHead1 == nullptr)
        {
            return pHead2;
        }
        if(pHead2 == nullptr)
        {
            return pHead1;
        }
        
        //建立一个表头
        ListNode* pHead = new ListNode(0);
        ListNode* cur = pHead;  
        
        //当两个链表都不为空时，两链表值比较，比较小的值尾插
        while(pHead1 && pHead2)
        {
            if(pHead1->val <= pHead2->val)
            {
                cur->next = pHead1;
                pHead1 = pHead1->next;
            }
            else
            {
                cur->next = pHead2;
                pHead2 = pHead2->next;
            }
            cur = cur->next;  //cur要后移，准备下一个的插入
        }
        
        //其中一个链表插完了，另一个还剩余，则直接连接在后面
        if(pHead1)
        {
            cur->next = pHead1;
        }
        if(pHead2)
        {
            cur->next = pHead2;
        }
        return pHead->next;  //头结点不包含数据
    }