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

合并两个排序的链表

http://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337

描述

这是一篇面对初级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