设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针，试设计一个算法,将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其它的存储空间。表中允许有重复的数据。

2022-06-03

设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针，试设计一个算法,将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其它的存储空间。表中允许有重复的数据。

答案：

解 #include template  class List;template  class ListNode {friend class List;public:    ListNode ();    //构造函数    ListNode ( const Type& item );    //构造函数private:    Type data;     ListNode *link;};template  class List {public:    List ( const Type finishied );    //建立链表    void Browse ( );    //打印链表    void Merge ( List  &hb );    //连接链表private:    ListNode *first,*last;};//各成员函数的实现    template     ListNode :: ListNode( ): link ( NULL){}//构造函数,仅初始化指针成员。    template  ListNode :: ListNode ( const Type & item ) : data ( item ), link (NULL){}    //构造函数,初始化数据与指针成员。    template  List :: List ( const Type finishied){    //创建一个带表头结点的有序单链表, finished 是停止建表输入标志,是所有输入值中不可能出现的数值。    first=last=new ListNode( );   //创建表头结点    Type value;    ListNode *p,*q, *s;    cin >> value;    while ( value != finished){    //循环建立各个结点    s=new ListNode( value );    q= first; p = first ->link;    while(p!= NULL && p->data <= value )    {q=p; p=p >link; }     //寻找新结点插入位置    q->link=s; s ->link= p;    //在q, p间插入新结点    if(p一NULL) last= s;    cin>>value;    }}template  void List :: Browse() {//浏览并输出链表的内容    cout<<"nThe List is:\n";    ListNode *p = first ->link;    while(p != NULL){    cout << p->data;    if(p!= last ) cout << "->";    else cout << endl;    p= p->link;    }}template  void List  :: Merge ( List& hb) {//将当前链表this 与链表hb按逆序合并，结果放在当前链表this中。    ListNode *pa, *pb, *q, *p;    pa=first->link; pb = hb.first->link;    //检测指针跳过表头结点    first->link = NULL;    //结果链表初始化    while (pa != NULL && pb != NULL){ /当两链 表都未结束时    if( pa->data<= pb->data )    {q-pa; pa = pa->link; }    //从pa链中摘下    else    {q= pb; pb= pb->link; }    //从pb链中摘下    q->link= first-link; first->link=q;    //链入结果链的链头}    p=(pa!=NULL)? pa: pb;    //处理未完链的剩余部分    while(p!= NULL){    q=p; p=p->link;    q->link = first->link;    first->link=q;    }}

举一反三

内容

0
假设有两个按元素值非递减次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值非递增次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。
1
对于双向链表,在两个结点之间插入一个新结点需修改的指针共（__）个，单链表为（__）个。
2
设有n个待排序元素存放在一个不带表头结点的单链表中，每个链表结点只存放一个元素,头指针为r。试设计一个算法，对其进行二路归并排序,要求不移动结点中的元素,只改各链结点中的指针,排序后r仍指示结果链表的第一个结点。(提示:先对待排序的单链表进行一次扫描,将它划分为若干有序的子链表，其表头指针存放在一个指针队列中。当队列不空时重复执行，从队列中退出两个有序子链表,对它们进行二路归并，结果链表的表头指针存放到队列中。如果队列中退出一个有序子链表后变成空队列，则算法结束。这个有序子链表即为所求。)
3
设一个有序的单链表中有n个结点,现要求插入一个新结点后使得单链表仍然保持有序,则该操作的时间复杂度为( )。
4
n个结点的链表中只含有2n +1个指针(包括头指针),且均为非空指针域,则该链表结构为（）。 A: 带表头结点的双向循环链表 B: 带表头结点的双向非循环链表 C: 不带表头结点的双向循环链表 D: 不带表头结点的双向非循环链表