方法1：
公式推导:定义两个指针，一个快指针，一个慢指针。两个指针一起走，快指针每次走两步，慢指针每次走一步（相当于速度不一样）。如果有环，那么它们就一定会相遇，当他们相遇时，走的次数是一样的（相当于时间），路程不一样。且，快指针的路程是慢指针的路程的2倍。这就的到了图中的第一个公式。将第一个公式进行一系列的化简，得出最后一个公式。
通过最后一个公式我们可以知道，如果有两个指针同时走，一个从相遇点出发（相当于少走了y），一个从链的起点出发，那么，它们一定会在环的入口点相遇的。
pNode GetCircleEntryNode(pNode meet, pList plist)//方法1 { pNode first = meet;//从相遇点出发 pNode second = plist;//从起点出发 if ((plist == NULL) || (meet==NULL))//相遇点为NULL，代表没有环 { return NULL; } while (first!=second) { first = first->next; second = second->next; } return first; }
方法2：
定义两个指针，第一个指针先走环的长度步，然后两个指针一起走，当他们相遇的时候停下来，相遇点便是入口点。
pNode GetCircleEntryNode(int len,pList plist)//方法2 { pNode first = plist; pNode second = plist; if ((plist == NULL)||(len==0))//环的长度为0，说明没有环 { return NULL; } while (len-->0)//第一个指针先走环的长度步 { first = first->next; } while (first!=second) { first = first->next; second = second->next; } return first; }
方法3：
从相遇点断开，就相当于有交点的两条链。将两条链的长度len1，len2分别求出来，用k来表示长度之差，哪个长一点，哪个就先走K步，K步走完后，长的链剩下的长度和短的链一样长，那么，它们到交点（环的入口）距离一样远，现在同时走，相遇点便是入口点。
pNode GetCircleEntryNode(pNode meet, pList plist)//方法3 { pNode first = meet; pNode second = plist; pNode cur = meet;//cur指针用于记住相遇点的位置，方便后边从此断开 int len1 = 0; int len2 = 0; if ((plist == NULL) || (meet == NULL)) { return 0; } first = first->next;//让first指针指向相遇点的下一个位置 cur->next = NULL;//将链表从相遇点断开，链表变成两条有交点的链 cur = first;//cur记住L1的起始位置，方便下一次便利的时候可以找到头 while (first!=NULL)//遍历L1，求出其长度len1 { ++len1; first = first->next; } while (second != NULL)//遍历L2，求出其长度了len2 { ++len2; second = second->next; } first = cur;//让first指针指向链L1的起点 second = plist;//让second指针指向链L1的起点 if (len1 > len2)//比较两条链的长度，两条链哪条长哪条先走 { int k = len1 - len2; while (k-- > 0) { first = first->next; } while (first != second)//让两个指针同时往后走走，指向同一点及交叉点时停下 { first = first->next; second = second->next; if (first == second) { return first; } } } else { int k = len2 - len1; while (k-- > 0) { second = second->next; } while (first != second) { first = first->next; second = second->next; if (first == second) { return first; } } } } 下边是相关函数的实现和测试代码
头文件和函数声明LinkNode.h部分
#ifndef __LINKLIST_H__ #define __LINKLIST_H__ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> typedef int DataType; typedef struct Node { DataType data; struct Node* next; }Node, *pNode, *pList; void InitLinkList(pList* pplist); //初始化 void PushFront(pList*pplist, DataType x);//前加 void Display(pList pl); //打印 void DestroyList(pList* pplist);//销毁 pNode Find(pList pl, DataType x); //查找函数 pNode CheckCycle(pList plist);//判断是否有环 int GetCircleLength(pNode meet);//求环的长度 pNode GetCircleEntryNode(pNode meet, pList plist);//求环的入口 //pNode GetCircleEntryNode(int len,pList plist) #endif //__LINKLIST_H__
各个函数的具体实现LinkNode.c部分
#include "LinkNode.h" void InitLinkList(pList* pplist)//初始化 { assert(pplist != NULL); *pplist = NULL; } void PushFront(pList*pplist, DataType x)//前加 { assert(pplist != NULL); pNode node = malloc(sizeof(Node)); if (node == NULL) { perror("malloc"); exit(EXIT_FAILURE); } node->data = x; node->next = NULL; node->next = *pplist; *pplist = node; } void Display(pList pl)//打印 { if (pl == NULL) { return; } while (pl != NULL) { printf("%d-->", pl->data); pl = pl->next; } printf("\n"); } void DestroyList(pList* pplist)//销毁 { assert(pplist != NULL); while (*pplist != NULL) { pNode tmp = (*pplist)->next; free(*pplist); (*pplist)->next = NULL; *pplist = tmp; } } pNode Find(pList pl, DataType x) //查找函数 { pNode head = pl; while (head->data != x) { head = head->next; } if (head->data == x) { return head; } else { return NULL; } } //判断是否有环 pNode CheckCycle(pList plist) { pNode fast = plist; pNode slow = plist; if (plist == NULL) { return NULL; } while ((fast != NULL) && (fast->next != NULL)) { fast = fast->next->next; slow = slow->next; if (fast == slow) { return fast; } } return NULL; } //求环的长度 int GetCircleLength(pNode meet) { pNode Meet = NULL; int count = 0; if (meet == NULL) { return count; } Meet = CheckCycle(meet); meet = Meet; Meet = Meet->next; count++; while (Meet != meet) { count++; Meet = Meet->next; } return count; } //求环的入口 //pNode GetCircleEntryNode(pNode meet, pList plist)//方法1 //{ // pNode first = meet;//从相遇点出发 // pNode second = plist;//从起点出发 // if ((plist == NULL) || (meet==NULL))//相遇点为NULL，代表没有环 // { // return NULL; // } // while (first!=second) // { // first = first->next; // second = second->next; // } // return first; //} // //pNode GetCircleEntryNode(int len,pList plist)//方法2 //{ // pNode first = plist; // pNode second = plist; // if ((plist == NULL)||(len==0))//环的长度为0，说明没有环 // { // return NULL; // } // while (len-->0)//第一个指针先走环的长度步 // { // first = first->next; // } // while (first!=second) // { // first = first->next; // second = second->next; // } // return first; //} pNode GetCircleEntryNode(pNode meet, pList plist)//方法3 { pNode first = meet; pNode second = plist; pNode cur = meet;//cur指针用于记住相遇点的位置，方便后边从此断开 int len1 = 0; int len2 = 0; if ((plist == NULL) || (meet == NULL)) { return 0; } first = first->next;//让first指针指向相遇点的下一个位置 cur->next = NULL;//将链表从相遇点断开，链表变成两条有交点的链 cur = first;//cur记住L1的起始位置，方便下一次便利的时候可以找到头 while (first!=NULL)//遍历L1，求出其长度len1 { ++len1; first = first->next; } while (second != NULL)//遍历L2，求出其长度了len2 { ++len2; second = second->next; } first = cur;//让first指针指向链L1的起点 second = plist;//让second指针指向链L1的起点 if (len1 > len2)//比较两条链的长度，两条链哪条长哪条先走 { int k = len1 - len2; while (k-- > 0) { first = first->next; } while (first != second)//让两个指针同时往后走走，指向同一点及交叉点时停下 { first = first->next; second = second->next; if (first == second) { return first; } } } else { int k = len2 - len1; while (k-- > 0) { second = second->next; } while (first != second) { first = first->next; second = second->next; if (first == second) { return first; } } } }
测试函数test.c部分
#include "LinkNode.h" void test() { pList list; int len = 0; pNode meet = NULL; pNode ret1 = NULL; pNode ret2 = NULL; pNode ret3 = NULL; InitLinkList(&list); PushFront(&list, 1); PushFront(&list, 2); PushFront(&list, 3); PushFront(&list, 4); PushFront(&list, 5); PushFront(&list, 6); PushFront(&list, 7); PushFront(&list, 8); PushFront(&list, 9); Find(list, 1)->next = Find(list, 5); meet = CheckCycle(list); len = GetCircleLength(meet); //验证方法1 //ret1 = GetCircleEntryNode(meet,list); /*if (ret1 == NULL) { printf("NOCYCLE\n"); } else { printf("the entry is:%d\n",ret1->data); }*/ //验证方法2 ret2 = GetCircleEntryNode(len, list); if (ret2 == NULL) { printf("NOCYCLE\n"); } else { printf("the entry is:%d\n", ret2->data); } //验证方法3 /*ret3 = GetCircleEntryNode(meet, list); if (ret3 == NULL) { printf("NOCYCLE\n"); } else { printf("the entry is:%d\n", ret3->data); }*/ } int main() { test(); return 0; }PS：想要验证哪种方法就就哪种方法的函数和测试代码放开就OK了。
