数据结构
合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下
——老子
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-