数据结构 | 每日一练（44）

数据结构

合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下

——老子

1

每日一练

1．知 L1、L2 分别为两循环单链表的头结点指针，m,n 分别为 L1、L2 表中数据结点个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。

类似本题的另外叙述有：

（1）试用类 Pascal 语言编写过程 PROC join（VAR la：link； lb：link） 实现连接线性表 la 和

lb(lb 在后)的算法，要求其时间复杂度为 0（1）， 占用辅助空间尽量小。描述所用结构。

（2）设有两个链表，ha 为单向链表，hb 为单向循环链表。编写算法，将两个链表合并成一个单向链表，要求算法所需时间与链表长度无关。

正确答案

ps：||代表注释

1．[题目分析]循环单链表L1和L2数据结点个数分别为m和n ，将二者合成一个循环单链表时，需要将一个循环链表的结点（从第一元素结点到最后一个结点）插入到另一循环链表的第一元素结点前即可。题目要求“用最快速度将两表合并“，因此应找结点个数少的链表查其尾结点。

LinkedList Union(LinkedList L1,L2; int m,n)∥L1和L2分别是两循环单链表的头结点的指针，m和n分别是L1和L2的长度。

∥本算法用最快速度将L1和L2合并成一个循环单链表。

{ if(m<0||n<0) {printf(“表长输入错误\n”)；exit(0);}

if(m<n) ∥若m<n，则查L1循环单链表的最后一个结点。

{ if(m==0) return(L2);∥L1为空表。

else{p=L1;

while(p->next!=L1) p=p->next;∥查最后一个元素结点。

p->next=L2->next;∥将L1循环单链表的元素结点插入到L2的第一元素结点前。

L2->next=L1->next;

free(L1);∥释放无用头结点。

}

}∥处理完m<n情况

else∥ 下面处理L2长度小于等于L1的情况

{ if(n==0) return(L1);∥L2为空表。

else{p=L2;

while(p->next!=L2) p=p->next;∥查最后元素结点。

p->next=L1->next;∥将L2的元素结点插入到L1循环单链表的第一元素结点前。

L1->next=L2->next;

free(L2);∥释放无用头结点。

}

}∥算法结束。

类似本题叙述的其它题解答如下：

（1）[题目分析]本题将线性表la和lb连接，要求时间复杂度为O（1），且占用辅助空间尽量小。应该使用只设尾指针的单循环链表。

LinkedList Union(LinkedList la,lb)

∥la和lb是两个无头结点的循环单链表的尾指针，本算法将lb接在la后，成为一个单循环链表。

{ q=la->next; ∥q指向la的第一个元素结点。

la->next=lb->next; ∥将lb的最后元素结点接到lb的第一元素。

lb->next=q; ∥将lb指向la的第一元素结点，实现了lb接在la后。

return(lb); ∥返回结果单循环链表的尾指针lb。

}∥算法结束。

[算法讨论]若循环单链表带有头结点，则相应算法片段如下：

q=lb->next; ∥q指向lb的头结点；

lb->next=la->next; ∥lb的后继结点为la的头结点。

la->next=q->next; ∥la的后继结点为lb的第一元素结点。

free(q); ∥释放lb的头结点

return(lb); ∥返回结果单循环链表的尾指针lb。

（2）[题目分析]本题要求将单向链表ha和单向循环链表hb合并成一个单向链表，要求算法所需时间与链表长度无关，只有使用带尾指针的循环单链表，这样最容易找到链表的首、尾结点，将该结点序列插入到单向链表第一元素之前即可。其核心算法片段如下（设两链表均有头结点）

q=hb->next; ∥单向循环链表的表头指针

hb->next=ha->next; ∥将循环单链表最后元素结点接在ha第一元素前。

ha->next=q->next; ∥将指向原单链表第一元素的指针指向循环单链表第一结点

free(q); ∥释放循环链表头结点。

若两链表均不带头结点，则算法片段如下：

q=hb->next; ∥q指向hb首元结点。

hb->next=ha; ∥hb尾结点的后继是ha第一元素结点。

ha=q; ∥头指针指向hb的首元结点。

如果您觉得本篇文章对您有作用，请转发给更多的人，点一下好看就是对小编的最大支持！

-end-