2. 考研
  3. 有两个单链表La和Lb，La中有m个元素，Lh中的元素个数为n。已知两个链表均为递增的单向链表。现想将两个链表归并成一个递增的单向链表，且希望利用原来的结点空间，请回答下列问题： (1)给出算法的主要思想； (2)写出算法的实现函数； (3)总

有两个单链表La和Lb，La中有m个元素，Lh中的元素个数为n。已知两个链表均为递增的单向链表。现想将两个链表归并成一个递增的单向链表，且希望利用原来的结点空间，请回答下列问题： (1)给出算法的主要思想； (2)写出算法的实现函数； (3)总

admin2014-07-18  86
问题 有两个单链表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->valueNext ->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://www.kaotiyun.com/show/Maxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)