首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
有两个单链表La和Lb,La中有m个元素,Lh中的元素个数为n。已知两个链表均为递增的单向链表。现想将两个链表归并成一个递增的单向链表,且希望利用原来的结点空间,请回答下列问题: (1)给出算法的主要思想; (2)写出算法的实现函数; (3)总
有两个单链表La和Lb,La中有m个元素,Lh中的元素个数为n。已知两个链表均为递增的单向链表。现想将两个链表归并成一个递增的单向链表,且希望利用原来的结点空间,请回答下列问题: (1)给出算法的主要思想; (2)写出算法的实现函数; (3)总
admin
2014-07-18
31
问题
有两个单链表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://kaotiyun.com/show/Maxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
第一国际开展了哪些活动?其内部经历了哪些主要斗争?
下列各组条约的时间排列顺序正确的是()①《布列斯特条约》②《色佛尔条约》③《九国公约》④《洛桑条约》
西藏自治区的设立时间是()。
美洲是一块古老的大陆,长期以来与世隔绝。把它与世界开始联系起来的重大转折时刻是()
1936年,张学良和杨虎城发动的西安事变()。①是一次具有爱国意义的兵变②民族矛盾激化的结果③检验了中国社会各阶级的抗日态度④促成了抗日民族统一战线初步形成
简述鸦片战争的三个阶段。
简述弭兵之会的背景、过程和结果。
“二战”期间,美国研制了原子弹并用于实践;1946年美国投入使用的第一台电子计算机最初是用于计算炮弹弹道的;德国人研制成功的远程液体火箭是用于空袭英国的。以上史实说明()。
西周的官僚制度已经相当完备,官僚机构庞杂,职官名目繁多。周王室的官僚机构分为两大系统,分别是()。
晚清时期清帝年号的正确排序是
随机试题
论述当前中国社会流动的特点。
A.外涂敷紫云膏B.樟脑软膏C.依沙吖啶氧化锌糊剂D.高锰酸钾溶液E.赛庚啶对轻度冻疮患者可以选用()。
一高压同轴圆柱电缆,内导体的半径为a,外导体的内半径为b,若b固定,要使内导体表面上场强最小,a与b的比值应该是()。
下列检测内容,不属于数字视频安防监控系统检测的是()。
甲乙两家公司联合投标一项工程,按招标公告规定的截止日期2012年3月10日送达了投标书,随后于3月11日签订了联合投标协议,则评标委员会初审该联合体的投标书时应()。
20×5年年初,客户因质量问题退回了X公司于20×4年12月赊销的产品,但X公司直接抵减了退回当月的销售收入,没有调整上年财务报表。注册会计师在编制20×4年审计调整分录时,应当()。
根据下列资料,回答下列问题。2013年1~7月份,某市规模以上工业增加值同比增长12.0%,增速比去年同期提高1.4个百分点。1~7月份,全市国有及国有控股企业完成增加值同比下降3.5%;民营企业完成增加值同比增长24.8%:外商控股企业完成增加值同比
下列关于犯罪未完成形态的说法错误的是()
Ifyouwanttoloseweight,butarenotafanofthegym,theresultsofanewstudycouldofferawelcomealternative.Peoplew
Now,morethanever,itdoesn’tmatterwhoyouarebutwhatyoulooklike.Janetwasjusttwenty-fiveyearsold.Shehadag
最新回复
(
0
)