合并两条有序链表

标签: 合并 链表 | 发表时间:2017-04-28 01:03 | 作者:qq_29503203
出处:http://blog.csdn.net

有序链表的合并是面试的时候常考的一道链表算法题:
输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则(即升序)。
对于这道题目有两种解法:一是非递归形式,二是递归形式。
1.非递归算法,我们解题思路如下:
(1)先考虑这几种特殊情况,
如果两条链表相等,我们将返回任意一条即可;
如果一条链表为空,另一条不为空,那么我们返回不为空的那条链表即可;
(2)这些情况处理完之后,我们再来进行下一步骤,
先确定两条不为空的链表排序后的头部,也就是比较第一个节点值的大小;
排序新链表头部确定好后,我们再来比较后面的值进行连接,这里维护一个尾指针比较好操作;
最后这个问题容易被忽略,比如说,链表1为 1->3->5;链表2为 2->4->6
在前面的步骤中已经将链表1处理完,但链表2里面还有6未处理,所以对于这种情况,我们就应该检测,如果一条链表已经为空(即处理完),另一条链表不为空时,我们就直接将不为空的链表链在排序新链表的尾部。
代码如下:

  struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};
   ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        if(pHead1==pHead2)
            return pHead1;
        if(pHead1==NULL)
            return pHead2;
        if(pHead2==NULL)
            return pHead1;

        ListNode* NewHead=NULL;
        ListNode* tail=NULL;
        ListNode* cur1=pHead1;
        ListNode* cur2=pHead2;
        if(cur1->val < cur2->val)
            {
            NewHead=cur1;
            tail=cur1;
            cur1=cur1->next;
        }
        else
        {
            NewHead=cur2;
            tail=cur2;
            cur2=cur2->next;
        }
        while(cur1 && cur2)
            {
            if(cur1->val < cur2->val)
                {
                tail->next=cur1;
                tail=tail->next;
                cur1=cur1->next;
            }
            else
                {
                tail->next=cur2;
                tail=tail->next;
                cur2=cur2->next;
            }
        }

        if(cur1==NULL)
            {
            tail->next=cur2;
            tail=tail->next;
        }
        else
            {
            tail->next=cur1;
            tail=tail->next;
        }
        return NewHead;
    }

2.递归方式
递归的问题就是考虑两件事情:一是递归结束条件,二是子问题的解决。
这里直接给出代码:

   ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        if(pHead1==pHead2)
            return pHead1;
        if(pHead1==NULL)
            return pHead2;
        if(pHead2==NULL)
            return pHead1;

        if(pHead1->val < pHead2->val)
            {
            pHead1->next=Merge(pHead1->next,pHead2);
            return pHead1;
        }
        else         // pHead1->val >= pHead2->val
            {
            pHead2->next=Merge(pHead1,pHead2->next);    
            return pHead2;
        }
作者:qq_29503203 发表于2017/4/27 17:03:47 原文链接
阅读:124 评论:0 查看评论

相关 [合并 链表] 推荐:

合并两条有序链表

- - CSDN博客编程语言推荐文章
有序链表的合并是面试的时候常考的一道链表算法题:. 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则(即升序). 对于这道题目有两种解法:一是非递归形式,二是递归形式. 1.非递归算法,我们解题思路如下:. (1)先考虑这几种特殊情况,. 如果两条链表相等,我们将返回任意一条即可;.

java合并PDF

- - Java - 编程语言 - ITeye博客
15.         * * 合並pdf文件 * * @param files 要合並文件數組(絕對路徑如{ "e:\\1.pdf", "e:\\2.pdf" ,. 17.         * 合並後新產生的文件絕對路徑如e:\\temp.pdf,請自己刪除用過後不再用的文件請 * @return boolean.

mysql-merge合并表

- - CSDN博客编程语言推荐文章
注意: 1 每个子表的结构必须一致,主表和子表的结构需要一致, 2 每个子表的索引在merge表中都会存在,所以在merge表中不能根据该索引进行唯一性检索. 3 子表需要是MyISAM引擎 4 AUTO_INCREMENT 不会按照你所期望的方式工作. 建表语句 create table tablename(正常的字段)engine=merge insert_method=last insert_method: 有两个值如下: LAST 如果你执行insert 指令来操作merge表时,插入操作会把数据添加到最后一个子表中.

合并和比较度量

- liang - SEM WATCH
往往我们在做分析的时候需要结合各类基本的指标进行二次计算合并得到一个可以用于进行综合评价或比较的度量,这个过程中就需要涉及到一些指标的合并技巧,和比较基准的设定. 其实之前“数据上下文”的系列文章中也一再强调了我们需要为指标设定合理的参考系来评价指标的趋势或表现的好坏,之前提供了一系列的方法,但这篇文章里面要介绍的方法应该是最简单方便的,同时不失实用性,得益于《用户体验度量》这本书中的介绍,所以这篇文章更像是一篇读书笔记,内容基本整理总结自《用户体验度量》第8章——合并和比较度量,当然不再局限于用户体验层面,结合了网站分析层面的思考.

ffmpeg裁剪合并视频

- - inJava
这里裁剪是指时间轴裁剪,不是空间裁剪. 比如说,你想把视频的从一分20秒开始,30秒的视频裁剪出来,保存成一个视频. ffmpeg提供简单的命令参数:. -ss 开始时间,如: 00:00:20,表示从20秒开始;. -t 时长,如: 00:00:10,表示截取10秒长的视频;. -i 输入,后面是空格,紧跟着就是输入视频文件;.

hive小文件合并

- - 互联网 - ITeye博客
    hive仓库表数据最终是存储在HDFS上,由于Hadoop的特性,对大文件的处理非常高效. 而且大文件可以减少文件元数据信息,减轻NameNode的存储压力. 但是在数据仓库中,越是上层的表汇总程度就越高,数据量也就越小,而且这些表通常会有日期分区,随着时间的推移,HDFS的文件数目就会逐步增加.

SVN:合并一个分支到主干

- - P.Linux Laboratory
本文内容遵从 CC版权协议, 可以随意转载, 但必须以超链接形式标明文章原始出处和作者信息及版权声明网址: http://www.penglixun.com/tech/program/svn_merge_branch_trunk.html. 原文在此,我只是翻译: http://www.sepcot.com/blog/2007/04/SVN-Merge-Branch-Trunk.

优化 RequireJS 项目(合并与压缩)

- - 博客 - 伯乐在线
英文原文: Optimize (Concatenate and Minify) RequireJS Projects,编译: oschina. 本文将演示如何合并与压缩一个基于RequireJS的项目. 本文中将用到苦干个工具,这其中就包括 Node.js. 因此,如果你手头上还没有Node.js可以 点击此处下载一个.

hbase权威指南: store file合并(compaction)

- - CSDN博客推荐文章
          hbase为了防止小文件(被刷到磁盘的menstore)过多,以保证保证查询效率,hbase需要在必要的时候将这些小的store file合并成相对较大的store file,这个过程就称之为compaction. 在hbase中,主要存在两种类型的compaction:minor  compaction和major compaction.

Hadoop Namenode HA 合并到主干

- - NoSQLFan
Hadoop 的 Namenode 单点问题一直广受诟病,而这个问题最近将会得到解决,对Namenode 的HA方案已经完成实施并合并到主干,经过严格的测试后将会在后续版本中发布. HA方案中,主要进行了如下的一些工作:. 其主要原理是将NameNode分为两种角色,Active和Standby,Active就是正在进行服务的NameNode,而Standby又分三种情况.