牛客题霸面试真题——链表：NC33 合并两个排序的链表

要求
时间复杂度为O(n)，说明只能存在一层循环。空间复杂度为O(1)，说明新申请的节点必须是有限个数，不能为新的结果链表的每个节点依次申请空间，也就是说只能连接新链表的next指针l来得出最终的结果。

class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode *newhead = new ListNode(-1);
        ListNode *p=newhead;
        while(pHead1&&pHead2){
            if(pHead1->valval){
                p->next=pHead1;
                pHead1=pHead1->next;
            }
            else{
                p->next=pHead2;
                pHead2=pHead2->next;
            }
            p=p->next;
        }
        if(pHead1==nullptr) p->next=pHead2;
        else p->next=pHead1;
        
        return newhead->next;
    }
};

复杂度分析：
时间复杂度O(N+M)：M N分别表示pHead1, pHead2的长度
空间复杂度O(1)：常数级空间

class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        //如果一个链表为空返回另外一个链表
        if(!pHead1) return pHead2;
        if(!pHead2) return pHead1;
        //pHead1->next节点应该为pHead1->next和pHead2合并后的节点
        if(pHead1->val < pHead2->val){
            pHead1->next = Merge(pHead1->next,pHead2);
            return pHead1;
        }
        //pHead2->next节点应该为pHead1和pHead2->next合并后的节点
        else{
            pHead2->next = Merge(pHead1,pHead2->next);
            return pHead2;
        }
    }
};

时间复杂度O(N+M)：M N分别表示pHead1, pHead2的长度
空间复杂度O(N+M)：迭代次数占用空间