## 問題描述 > 給定兩個單鏈表，編寫算法找出兩個鏈表的共同結點 ## 算法思想 > 我們從[單鏈表的定義](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就是因為此單鏈表都是自己創建的，所以公共結點在哪兒一開始就已經知道了。然后睜著眼睛說了半天瞎話……