首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
有两个单链表La和Lb,La中有m个元素,Lh中的元素个数为n。已知两个链表均为递增的单向链表。现想将两个链表归并成一个递增的单向链表,且希望利用原来的结点空间,请回答下列问题: (1)给出算法的主要思想; (2)写出算法的实现函数; (3)总
有两个单链表La和Lb,La中有m个元素,Lh中的元素个数为n。已知两个链表均为递增的单向链表。现想将两个链表归并成一个递增的单向链表,且希望利用原来的结点空间,请回答下列问题: (1)给出算法的主要思想; (2)写出算法的实现函数; (3)总
admin
2014-07-18
38
问题
有两个单链表La和Lb,La中有m个元素,Lh中的元素个数为n。已知两个链表均为递增的单向链表。现想将两个链表归并成一个递增的单向链表,且希望利用原来的结点空间,请回答下列问题:
(1)给出算法的主要思想;
(2)写出算法的实现函数;
(3)总结所用算法的时间和空间复杂度。
选项
答案
(1)基本思想:遍历链表La和Lb,将其元素值进行比较,再合并成一个递增的单向链表。 (2)算法的实现如下: 链表结点定义为: struct node{ int value; struct node*Next: }; struct node *merge(struct node*a,struct node*b){ struct node *P; struct node *q; struct node *t; if(a->value<=b->value){//比较当前指针所指值的大小 P=a: q=b; }else{ P=b: q=a: } t=P: while(q){//如果b链表先结束,那么将a链表剩余结点全部合并到新链表 if(p->Next==NULL){ p->Next=q; break: } if(q->value
Next ->Value){ struct node * k=q->Next; q->Next=p->Next; p=p->Next; q=k; continue; } p=p->Next; } return t: } (3)遍历链表的时间复杂度为O(max(m,n)),算法实现过程中使用的辅助空间为常量,空间复杂度为O(1)。
解析
转载请注明原文地址:https://jikaoti.com/ti/1UajFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简述战后西欧经济的变化过程。
1971年9月美苏英法四国签署(),肯定了西柏林的占领制度,柏林问题得以解决。
1938年,英、法、德、意在德国召开会议讨论对捷克斯洛伐克的苏台德地区的问题,这次会议被称为(),它把英法的绥靖政策推到了顶峰,加速了二战的爆发。
()一书对日月食的记录非常翔实,最早的一次是鲁隐公三年二月(公元前720年2月20日)的日全食,比西方的记录早了130多年。
撰写《南海寄归内法传》和《大唐西域求法高僧传》二书,记录了南亚许多国家的社会、文化和宗教状况,成为研究7世纪印度、巴基斯坦和南洋各国历史、地理可靠资料的是()。
1936年,张学良和杨虎城发动的西安事变()。①是一次具有爱国意义的兵变②民族矛盾激化的结果③检验了中国社会各阶级的抗日态度④促成了抗日民族统一战线初步形成
晚清时期清帝年号的正确排序是
对下列4个序列用快速排序方法进行排序,以序列的第1个元素为基准进行划分。在第1趟划分过程中,元素移动次数最多的是()。
下列叙述正确的个数是()。 1)向二叉排序树中插入一个结点,所需比较的次数可能大于此二叉排序树的高度。2)对B-树中任一非叶子结点中的某关键字K,比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。3)所谓平衡二叉树是指左、右
现有一个解决无向连通图的最小生成树的一种方法如下:将图中所有边按权重从大到小排序为(el,e2,…,em);i=1;while(所剩边数>=顶点数){从图中删去ei;若图不再连通。则恢复ei;i=
随机试题
工业纯铝的线膨胀系数约为低碳钢的()。
(2010年4月)“不得包养情人”属于行政机关公务员应该遵守的______。
目前调强实现的方式有
案情:甲与乙分别出资60万元和240万元共同设立新雨开发有限公司(下称新雨公司题),由乙任执行董事并负责公司经营管理,甲任监事。乙同时为其个人投资的东风有限责任公司(下称东风公司题)的总经理,该公司欠白云公司货款50万元未还。乙与白云公司达成协议约定:若3
在现浇普通钢筋混凝土楼盖时,控制裂缝的主要施工措施有()。
下列方案中哪个方案能满足防火规范?[2006年第38题]
实行财政直接支付的支出包括()。
儿童对勇敢和冒险不能分辨主要是他们的抽象逻辑思维水平比较低的缘故。()
(2012联考48)由细颗粒物造成的灰霾天气对人体健康的危害要比沙尘暴更大。粒径10微米以上的颗粒物会被挡在人的鼻子外面;粒径在2.5微米至10微米的颗粒物,能够进入上呼吸道,但部分可通过痰液等排出体外,另外也会被鼻腔内部的绒毛阻挡,对人体健康危害相对较小
下列各项中不属于法人变更的是()。
最新回复
(
0
)