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


问题描述

输入两个递增排序的链表,合并这两个链表并使新链表中的结点仍然是按照递增排序的。
合并链表示意图
如图所示,链表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
阅读 534 讨论 0 喜欢 0

讨论

周娱

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

5531 1698621
抢先体验

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

加入组织

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

闪念胶囊

大多数人程序员都高估了他们一天能完成的开发量,但低估了他们一年能学习到的东西。 ​​​

“决定我们成为什么样的人,不是我们的能力,而是我们的选择。”

让一个团队走向平庸的最佳方式,是让成员们持续地干那些不让他们感到自豪的事情。

最近1 2年发现成长的最好方式是研究开源的项目,自己实践。成长速度非常的快,一个好的项目需要考虑的细节很多。

不积跬步无以至千里,越焦虑越要扎实干。

不要试图鹤立鸡群,趁早离开那群鸡!

程序员过节需要的不是美女、不是美食、不是不加班!他们需要的是写代码,一群人写、往死里写、通宵写!!那种暗流涌动的狂欢,远比虚无庸俗的食色更让他们振奋!! by芋头

面试的时候,常常会问数组和链表的区别,很多人都回答说,“链表适合插入、删除,时间复杂度 O(1);数组适合查找,查找时间复杂度为 O(1)”。 实际上,这种表述是不准确的。数组是适合查找操作,但是查找的时间复杂度并不为 O(1)。即便是排好序的数组,你用二分查找,时间复杂度也是 O(logn)。 所以,正确的表述应该是,数组支持随机访问,根据下标随机访问的时间复杂度为 O(1)。

找一个bug就好比从一泡烂泥里找一条泥鳅,写一个bug就好比往一泡烂泥里丢一条泥鳅进去

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