专栏首页深度学习与计算机视觉算法-合并两个排序的链表

算法-合并两个排序的链表

题目: 输入两个递增排序的链表,合并着两个链表并使新链表中的结点仍然是按照递增顺序的。例如输入的链表1和链表2如下,合并后的为链表3。链表的结点定义如下:

struct ListNode
{
  int value;
  ListNode *next;
};

解题思路: 首先可以确定的是,链表1和链表2本身就是递增的,所以合并的过程可以从链表1,2的头结点开始,先比较1,2的头结点中值的大小,将小的值的结点(比如为链表1头结点)作为合并后的链表(链表3)的头结点。随后可以考虑成链表1的从原链表第二个结点开始,再次重复上面的步骤,这样就变成了一个递归问题。

代码实现:

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

    ListNode* pMergedHead = NULL;

    if(pHead1->value < pHead2->value)
    {
        pMergedHead = pHead1;
        pMergedHead->next = Merge(pHead1->next, pHead2);
    }
    else
    {
        pMergedHead = pHead2;
        pMergedHead->next = Merge(pHead1, pHead2->next);
    }

    return pMergedHead;
}

测试例程:

#include<iostream>
using namespace std;

struct ListNode
{
int value;
ListNode *next;
};
void ShowList(ListNode* L);
void CreateList(ListNode * L,int n,int initial);
ListNode* Merge(ListNode* pHead1, ListNode* pHead2);
int main()
{
    ListNode * L1 = new ListNode;
    L1->next = nullptr;
    ListNode * L2 = new ListNode;
    L2->next = nullptr;
    CreateList(L1,4,1);
    CreateList(L2,4,2);
    ShowList(L1);
    ShowList(L2);
    ListNode * L3 = Merge(L1,L2);
    ShowList(L3);
    getchar();
    return 0;
}
void CreateList(ListNode * L,int n,int initial)
{
    L->value = initial;//输入第一个结点的数据值
    n--;
    for (int i = 0; i < n; i++)
    {   
        initial = initial+2;
        ListNode * p = new ListNode;
        p->value = initial;
        p->next = nullptr;
        L->next = p;
        L = p;
    }
}
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
    if(pHead1 == NULL)
        return pHead2;
    else if(pHead2 == NULL)
        return pHead1;

    ListNode* pMergedHead = NULL;

    if(pHead1->value < pHead2->value)
    {
        pMergedHead = pHead1;
        pMergedHead->next = Merge(pHead1->next, pHead2);
    }
    else
    {
        pMergedHead = pHead2;
        pMergedHead->next = Merge(pHead1, pHead2->next);
    }

    return pMergedHead;
}
void ShowList(ListNode* L)
{
    ListNode *p =L;
    while (p)
    {
        cout<<p->value<<' ';
        p=p->next;
    }
    cout<<endl;
}

结果如下:

个人感觉值得注意的地方有下面几个:

(1)如果链表1,2为空,要考虑代码的鲁棒性。

(2)要考虑链表1,2中某结点的数值相等的情况,这个在else中包含了。

(3)递归调用何时退出? 递归退出的条件与为了防止空链表造成异常的判断是一个:

    if(pHead1 == NULL)
        return pHead2;
    else if(pHead2 == NULL)
        return pHead1;

这就是这个代码很巧妙的地方,往往使一行代码两个甚至多个作用,我们举这样的例子: 链表1 : 1 3 链表2 : 2 4 首先执行Merge(1,2)函数,进入if, 进入第一次递归,执行Merge(3,2),显然会进入else, 进入第二次递归,执行Merge(3,4),显然会进入if, 进入第三次递归,执行Merge(NULL,4),此时就进入了是否为空的判断,并返回4,同时递归结束。

(4)新的链表何时链接? 我们可以这样理解这件事,还是上面的例子: 链表1 : 1 3 链表2 : 2 4 代码会第一次进入后再递归三次,递归结束后要return四次(从里向外),每一次return时都会将链表向前链接一个结点,每一次return的结果其实是这样: 1. 4 2. 3 4 3. 2 3 4 4.1 2 3 4

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 15个顶级Java多线程面试题及答案

    在任何Java面试当中多线程和并发方面的问题都是必不可少的一部分。如果你想获得任何股票投资银行的前台资讯职位,那么你应该准备很多关于多线程的问题。在投资银行业务...

    Java后端工程师
  • 让大象起舞:HTTPS 计算性能优化

    HTTPS 很安全,与此同时却又要消耗非常多的CPU资源,STGW 针对 nginx 和 openssl 进行了大量优化,用以提升 HTTPS 的计算性能和访问...

    腾讯技术工程官方号
  • 腾讯赵建春:AI浪潮下的高效运维思考及实践

    腾讯 SNG 助理总经理、GOPS 金牌讲师赵建春老师受邀出席大会,并带来精彩演讲《AI 浪潮下的高效运维思考与实践》。

    织云平台团队
  • 非极大值抑制(Non-Maximum Suppression)

    博客:noahsnail.com  |  CSDN  |  简书 |   云+社区

    Tyan
  • 京东首届”JDD-2017京东金融全球数据探索者大赛”中国区算法组落下帷幕

    2月17日,在经历了48小时的极限挑战之后,首届”JDD-2017京东金融全球数据探索者大赛”算法组全球总决赛和商业组中国区决赛落下帷幕。算法组四大赛题冠军分别...

    人工智能的秘密
  • 深度学习与强化学习

    随着 DeepMind 公司的崛起,深度学习和强化学习已经成为了人工智能领域的热门研究方向。除了众所周知的 AlphaGo 之外,DeepMind 之前已经使用...

    张戎
  • FPGA : 用“芯”做图

    图像的压缩,从本质上是通过提高计算算力来降低存储和带宽。同时更加复杂的算法也带来计算算力的大量消耗和处理延时的增加。

    腾讯架构师
  • 全面、简单理解朴素贝叶斯(Naive Bayes)

    朴素贝叶斯(Naive Bayes)是经典的机器学习算法之一,也是为数不多的基于概率论的分类算法。本文可能是目前网络上最全面也最简单易懂的有关朴素贝叶斯的文章。

    挖掘大数据
  • 算法:大O符号解释

    O(n),O(1),O(log n)等大O符号被用来表示算法的效率。在这篇文章中,你会找到每个大O符号的例子和解释。

    大数据弄潮儿
  • 神经网络模型求解思路

    神经网络模型,mini_batch 批梯度下降(SGD)求解权重参数的原理见:深度学习|神经网络模型简介和梯度下降求解,这篇文章中用一个小球下坡,解释了各个节点...

    人工智能的秘密

扫码关注云+社区

领取腾讯云代金券