Q:如何判断一个单链表是否有环，如果有环，找出环的入口点？
A:首先我们判断链表是否有环，设置两个指针slow和fast，指向单链表的头部，每个循环slow走一步，fast走两步。如果没有环，fast或者fast的next会走到NULL，否则fast在环里循环最终会和slow相遇，此时即存在环。
再看第二个问题，当slow和fast相遇时，假设fast已经在环内循环n圈，环长为r，同时fast走的长度为slow走的长度的两倍，设slow走了s步，则有
2*s=s+n*r => s=n*r，再设单链表头部到环入口的距离为a，环入口到相遇点得距离为x，则a+x=s=n*r，因此从单链表头部到相遇点的距离为环长的整数倍，因此我们可以将slow或fast指向单链表头部，和另外一个指针每次一步往前走，则再次相遇时他们同时指向的就是环的入口点。
1 struct Node 2 { 3 int value; 4 Node* next; 5 }; 6 7 8 Node* FindLoopEntrance(Node* head) 9 { 10 Node *slow,*fast; 11 slow=head; 12 fast=head; 13 while(fast && fast->next) 14 { 15 slow=slow->next; 16 fast=fast->next->next; 17 if(slow==fast) 18 break; 19 } 20 21 //无环 22 if(!fast || !fast->next) 23 return NULL; 24 25 slow=head; 26 while(slow!=fast) 27 { 28 slow=slow->next; 29 fast=fast->next; 30 } 31 return slow; 32 }
Q:找出两个单链表的第一个公共结点。
A:
方法1：将第一个单链表首尾连接，判断第二个单链表有没有环，如果有则说明两个单链表相交，此时可以求出第二个单链表的环入口结点，即为第一个公共结点。
方法2：如果两个单链表相交，则他们从第一个公共结点到最后一个结点肯定都相同，此时求出两个单链表的长度lenA和lenB，假设lenA>lenB,则将指向A链表头的指针先前进(lenA-lenB)步，而指向B链表的指针此时还指向B链表头，然后再将两个链表每次各走一步，则相遇就在第一个公共结点。