链表专项练习题三 | 合并两个有序链表


问题描述

输入两个递增排序的链表,合并这两个链表并使新链表中的结点仍然是按照递增排序的。
合并链表示意图
如图所示,链表1与链表2合并,最终得到链表3。

问题分析

因为两个链表上的结点都是递增排序的,合并后的链表也是递增排列的,那么合并后的链表头结点一定是两个链表头结点中较小的那一个。
我们可以先取出最小结点,然后再次对比两个链表的头结点,再次取出最小结点,依次处理,直至其中一个链表取空,然后将另一个链表所剩的结点全部拼接在合并链表的最后,即可完成对两个链表的递增合并。
如图所示
链表合并示意图

代码实现

递归法:

ListNode* Merge(ListNode* pHead1,ListNode* pHead2)
{
    if(pHead1==NULL)  return pHead2;
    if(pHead2==NULL)  return pHead1;
    
    ListNode* pMergeHead = NULL;
    if( pHead1->m_nValue < pHead2->m_nValue )
    {
        pMergeHead = pHead1;
        pMergeHead->m_pNext = Merge( pHead1->m_pNext , pHead2->m_pNext );
    }else{
        pMergeHead = pHead2;
        pMergeHead->m_pNext = Merge( pHead1->m_pNext , pHead2->m_pNext );
    }
    return pMergeHead;
}

迭代法:

ListNode* Merge(ListNode* pHead1,ListNode* pHead2)
{
    if(pHead1==NULL)  return pHead2;
    if(pHead2==NULL)  return pHead1;
    
    ListNode* pMergeHead = NULL;
    // 获取头结点
    if( pHead1->m_nValue < pHead2->m_nValue )
    {
        pMergeHead = pHead1;
        pHead1 = pHead1->m_pNext;
    }else{
        pMergeHead = pHead2;
        pHead2 = pHead2->m_pNext;
    }
    // 处理中间结点
    while( pHead1 != NULL && pHead2 != NULL ){
        if( pHead1->m_nValue < pHead2->m_nValue )
        {
            pMergeHead->m_pNext = pHead1;
            pHead1 = pHead1->m_pNext;
        }else{
            pMergeHead->m_pNext = pHead2;
            pHead2 = pHead2->m_pNext;
        }
    }
    // 处理剩余结点
    if( pHead1 != NULL ){
        pMergeHead->m_pNext = pHead1;
    }elseif( pHead2 != NULL ){
        pMergeHead->m_pNext = pHead2;
    }
    return pMergeHead;
}

参考链接

合并两个有序链表
合并两个有序单链表

本文发表于2018年11月14日 21:03
阅读 1445 讨论 0 喜欢 0

讨论

周娱

君子和而不同
按照自己的方式,去度过人生

7803 2937311
抢先体验

扫码体验
趣味小程序
文字表情生成器

加入组织

扫码添加周娱微信
备注“加入组织”
邀请进开发群

闪念胶囊

这个世界上,别人只会看你现在的样子而不是以后的样子。你以后的样子只有自己才相信。如果没有执行力,一切都是虚妄。

对普通人来说,人和人相处其实最重要的是感觉。感觉不好,你说什么都没用,怎么解释都没用,越说越错,反正最后不好的锅都往你身上扣。所谓“说你行你就行,不行也行。说你不行,你就不行,行也不行”就是这个意思。狼要吃人根本不需要理由,你也同样叫不醒装睡的人。遇到这种情况,早点闪人才是上策。不过大部分人的问题是没有闪人的心态,能力,和资源。

考985不牛逼,考上才牛逼。创业不牛逼,创业成功才牛逼。这个社会上很多人把目标当成牛逼的资本,牛逼哄哄的,死活不听劝,然后做的一塌糊涂,给别人添麻烦,让别人帮他料理后事,对此只能呵呵。

当你尝到用生气解决问题的甜头后,你就懒得再用其他方式了。你却忽略了,生气是鸩毒啊,剂量用够了,你的关系也玩完了。

年轻的时候你只搞事业不谈恋爱,等你事业有成了,钱相对自由了,你可能已经没有荷尔蒙了。

如果你经常雇佣比你矮小的人,将来我们就会变成矮人国,变成一家侏儒公司。相反,如果你每次都雇用比你高大的人,日后我们必能成为一家巨人公司。

如果一个人有充裕的时间去完成一项工作,那么他就会放慢节奏或者增加其他不必要的工作,直到花光所有的时间。

天空不是人类休息的地方,人类应该去亲近海洋。

一个人的正直程度,取决于他肯为原则付出的牺牲。

Copyright ? 2016 - 2018 Cion.
All Rights Reserved.
备案:鲁ICP备16007319号.