## 问题描述 > 给定两个单链表，编写算法找出两个链表的共同结点 ## 算法思想 > 我们从[单链表的定义](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<stdio.h> #include<stdlib.h> 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就是因为此单链表都是自己创建的，所以公共结点在哪儿一开始就已经知道了。然后睁着眼睛说了半天瞎话……