描述

这是一篇面对初级coder的题解。
知识点：链表
难度：二星

题解

题目：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

考察链表的基础知识

方法一：采用新链表合并

思路：创建一个新链表，将两个旧链表按顺序合入，至一个链表为空，将另一个链表接在后面。

算法流程：
初始化： 伪头节点 
 ListNode* vhead=new ListNode(-1); //一个技巧 初始化虚拟虚拟头结点，使每一个结点都有一个前驱结点便于循环
循环合并： 
            if(pHead1->val<=pHead2->val) //哪个链表头节点小从哪个链表拿
            {
                newhead->next=pHead1; //取节点
                pHead1=pHead1->next;//后移对应链表
            }
            else//同理
            {
                newhead->next=pHead2;
                pHead2=pHead2->next;
            }
            newhead=newhead->next;//将新链表后移
为空时跳出； 
while(pHead1&&pHead2)//终止条件 一个链表为空

合并剩余尾部： 跳出时有两种情况， 
        if(pHead2==nullptr) //将剩余的链表拼在后面
            newhead->next=pHead1;
        if(pHead1==nullptr)
            newhead->next=pHead2;

返回值： 合并链表在伪头节点 之后，因此返回 
vhead->next
即可。

class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode* vhead=new ListNode(-1); //一个技巧 初始化虚拟虚拟头结点，使每一个结点都有一个前驱结点便于循环
        ListNode *newhead=vhead;
        while(pHead1&&pHead2)//终止条件 一个链表为空
        {
            if(pHead1->val<=pHead2->val) //哪个链表头节点小从哪个链表拿
            {
                newhead->next=pHead1; //取节点
                pHead1=pHead1->next;//后移对应链表
            }
            else//同理
            {
                newhead->next=pHead2;
                pHead2=pHead2->next;
            }
            newhead=newhead->next;//将新链表后移
        }
        if(pHead2==nullptr) //将剩余的链表拼在后面
            newhead->next=pHead1;
        if(pHead1==nullptr)
            newhead->next=pHead2;
        return vhead->next;
    }
};


两个表都遍历了一遍，时间复杂度O(m+n)，同时由于没开新的空间存放表 空间复杂度O(1) 其中mn是两个链表的长度
运行时间： 5 ms 占用内存：608K

方法二：插入

将链表头小的作为主链表，将另一个链表插入其中 

class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode* ans;// 答案输出
        ListNode *temp;//插入缓存
        //防止一个链表为空 返回另一个
        if(!pHead1)     
            return pHead2;
        if(!pHead2)
            return pHead1;
        if(pHead1->val>pHead2->val) //哪个链表头节点小从哪个链表拿 保证是将pHead2插入pHead1
        {
            temp=pHead1;
            pHead1=pHead2;
            pHead2=temp;
        }
        ans=pHead1;
         while(pHead1->next&&pHead2)//终止条件 一个链表为空
        {
            if(pHead1->next->val>pHead2->val) //
            {
                temp=pHead1->next;//插入
                pHead1->next=pHead2;
                pHead2=pHead2->next;//后移对应链表2
                pHead1->next->next=temp;
            }
            pHead1=pHead1->next;//后移对应链表1
        }
        if(pHead1->next==nullptr) //将剩余的链表2拼在后面
            pHead1->next=pHead2;
        return ans;
    }
};

两个表都遍历了一遍，时间复杂度O(m+n)，同时由于没开新的空间存放表其中mn是两个链表的长度
空间复杂度O(1)
运行时间： 12 ms 占用内存：540K

总结

各位牛友在练习的时候要注意边界条件的判定
一般创建单链表，都会设一个虚拟头结点，也叫哨兵，因为这样每一个结点都有一个前驱结点。