第1章第2节练习题9 查找公共结点
最后更新于：2022-04-01 19:50:56
## 问题描述
> 给定两个单链表，编写算法找出两个链表的共同结点
## 算法思想
> 我们从[单链表的定义](http://blog.csdn.net/u013595419/article/details/50481785#t0)中可以发现每一个结点只有一个next域，那么从第一个公共结点开始，后面所有的结点都应该是重合的，形状应该类似与倒Y型（“`>-`”）。既然如此，那么对两条单链表同时开始遍历，只要它们的指针同时指向同一个结点（即：两指针相等）时不就找到公共结点了吗？
但在实现的时候，应该注意到，两张链表在等长的情况下，同时开始遍历，指针必然可以同时指向公共结点；可是如果不等长的话，同时遍历是无法同时指向公共结点的。
这里总结下思想核心
> - 分别求出两条单链表的长度len1和len2以及长度之差len；
> - 让LongPoint指针指向长度较长的单链表，让ShortPoint指针指向长度较短的单链表；
> - 对齐两条单链表的表尾，让长链表先遍历 len个结点；
> - 长短单链表同时开始遍历，直到指针LongPoint与指针ShortPoint指向同一个结点（相等）时为止。
## 算法描述
~~~
LNode* FindCommon(LNode* head1, LNode* head2)
{
int len1=ListLength(head1);//求链表1的长度
int len2=ListLength(head2);//求链表2的长度
int len; //长短单链表长度差
LNode *LongPoint; //指向长链表
LNode *ShortPoint; //指向短炼表
//判断长短链表
if(len1>len2){
len=len1-len2;
LongPoint=head1->next;
ShortPoint=head2->next;
}else{
len=len2-len1;
LongPoint=head2->next;
ShortPoint=head1->next;
}
//长链表先遍历长短链表长度差个结点
while(len--){
LongPoint=LongPoint->next;
}
//长短链表同时开始遍历
while(LongPoint!=NULL){
if(LongPoint==ShortPoint){
return LongPoint;
}
else{
LongPoint=LongPoint->next;
ShortPoint=ShortPoint->next;
}
}
return NULL;
}
~~~
具体代码见附件。
## 附件
~~~
#include
#include
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
LinkList CreatList(LNode*);
LNode* FindCommon(LNode*,LNode*);
int ListLength(LNode*);
void Print(LNode*);
int main(int argc, char* argv[])
{
LNode *head1;
head1=(LNode*)malloc(sizeof(LNode));
head1->next=NULL;
head1=CreatList(head1);
printf("Head1: ");
Print(head1);
int i=4;
LNode *p=head1;
while(i--){
p=p->next;
}
LNode *head2;
head2=(LNode*)malloc(sizeof(LNode));
head2=CreatList(head2);
LNode *r=head2->next;
while(r->next){
r=r->next;
}
r->next=p;
printf("head2: ");
Print(head2);
LNode *head;
head=(LNode*)malloc(sizeof(LNode));
head->next=NULL;
head->next=FindCommon(head1, head2);
printf("head: ");
Print(head);
return 0;
}
//尾插法建立单链表
LinkList CreatList(LNode *head)
{
LNode *r=head;
LNode *L;
ElemType x;
scanf("%d",&x);
while(x!=999){
L=(LNode*)malloc(sizeof(LNode));
L->data=x;
r->next=L;
r=L;
scanf("%d",&x);
}
r->next=NULL;
return head;
}
//寻找公共结点
LNode* FindCommon(LNode* head1, LNode* head2)
{
int len1=ListLength(head1);
int len2=ListLength(head2);
int len;
LNode *LongPoint;
LNode *ShortPoint;
if(len1>len2){
len=len1-len2;
LongPoint=head1->next;
ShortPoint=head2->next;
}else{
len=len2-len1;
LongPoint=head2->next;
ShortPoint=head1->next;
}
while(len--){
LongPoint=LongPoint->next;
}
while(LongPoint!=NULL){
if(LongPoint==ShortPoint){
return LongPoint;
}
else{
LongPoint=LongPoint->next;
ShortPoint=ShortPoint->next;
}
}
return NULL;
}
//求单链表长度
int ListLength(LNode *head)
{
LNode *p=head;
int count=0;
while(p){
++count;
p=p->next;
}
return count;
}
//打印全部结点
void Print(LNode *head)
{
LNode *p=head->next;
while(p){
printf("%4d",p->data);
p=p->next;
}
printf("\n");
}
~~~
注：
本源代码的主函数部分中，首先创建了单链表1，然后遍历单链表1四个结点，接着让单表2的尾结点的next域指向单链表1的第四个结点，从而形成两条具有公共结点的单链表。
故此代码中最大的Bug就是因为此单链表都是自己创建的，所以公共结点在哪儿一开始就已经知道了。然后睁着眼睛说了半天瞎话……
';