转自
dancingrain判断链表中是否有环 ----- 有关单链表中环的问题
首先，关于单链表中的环，一般涉及到一下问题：
1.给一个单链表，判断其中是否有环的存在；
2.如果存在环，找出环的入口点；
3.如果存在环，求出环上节点的个数；
4.如果存在环，求出链表的长度；
5.如果存在环，求出环上距离任意一个节点最远的点（对面节点）；
6.（扩展）如何判断两个无环链表是否相交；
7.（扩展）如果相交，求出第一个相交的节点；
1、判断单链表是否有环
思路：
- 暴力：给定一个足够大的循环上限，遍历链表，遍历到空指针则没有环，到达循环上限则认为有环。
- 做标记：将访问过的节点做上标记，每次访问新的节点都先看看该节点是否带标记。两种标记方法，一是修改节点的值为某个特定值，来表示已经访问过了；二是将访问过的节点存入set。
- 快慢指针：快指针一次走两步，慢指针一次走一步。
1 struct ListNode{ 2 int val; 3 ListNode *next; 4 5 ListNode(int x) : val(x), next(nullptr) { } 6 }; 7 8 // 1暴力 9 #define MAXTIMES 10000 10 bool hasCycle1(ListNode *head) 11 { 12 ListNode *p = head; 13 int i = 0; 14 while ((i < MAXTIMES) && (p != nullptr)) 15 { 16 p = p->next; 17 i++; 18 } 19 20 return p != nullptr; 21 } 22 23 24 // 2做标记 25 #include <set> 26 bool hasCycle2(ListNode *head) 27 { 28 std::set<ListNode*> marked; 29 ListNode *p = head; 30 31 while (p) 32 { 33 if(marked.find(p) != marked.end()) 34 return true; 35 else 36 { 37 marked.insert(p); 38 p = p->next; 39 } 40 } 41 42 return false; 43 } 44 45 // 3快慢指针 46 bool hasCycle3(ListNode *head) 47 { 48 ListNode *fast, *slow; 49 fast = slow = head; 50 51 while (slow and fast and fast->next) 52 { 53 slow = slow->next; 54 fast = fast->next->next; 55 if (slow == fast) 56 return true; 57 } 58 return false; 59 }
2、如果存在环，找出环的入口点
从上面的分析知道，当fast和slow相遇时，slow还没有走完链表，假设fast已经在环内循环了n(1<= n)圈。假设slow走了S步，因为fast每次走2步，则fast走了2*S步，又由于
fast走过的步数 = S + n * R（S + 在环上多走的n圈），则有下面的等式：
2 * S= S + n * R ;
=> S = n * R；
如果假设整个链表的长度是L，入口和相遇点的距离是x（如上图所示），起点到入口点的距离是a(如上图所示)，则有：
a + x = S = n * R;
a + x = (n - 1) * R + R = (n - 1) * R + (L - a)
=> a = (n - 1) * R + (L -a -x)
结论：从链表起点head开始到入口点的距离a,与从slow和fast的相遇点到入口点的距离加上若干个环的长度之和相等。换句话说，如果有两个指针p1, p2分别从head和相遇的点出发，他们最终一定会在环入口点相遇。
1 struct ListNode{ 2 int val; 3 ListNode *next; 4 5 ListNode(int x) : val(x), next(nullptr) { } 6 }; 7 8 9 // 快慢指针 10 ListNode* cycleEnterPoint(ListNode *head) 11 { 12 ListNode *fast, *slow; 13 fast = slow = head; 14 // 寻找相遇点 15 ListNode *meetPoint = nullptr; 16 while (slow and fast and fast->next) 17 { 18 slow = slow->next; 19 fast = fast->next->next; 20 if (slow == fast) 21 { 22 meetPoint = slow; 23 break; 24 } 25 } 26 // 寻找入口点 27 ListNode *p1 = head; 28 ListNode *p2 = meetPoint; 29 while (p1 != nullptr and p2 != nullptr and p1 != p2) 30 { 31 p1 = p1->next; 32 p2 = p2->next; 33 } 34 35 return p1; 36 }
3、如果存在环，求出环上节点的个数
思路：
1.记录下相遇节点存入临时变量tempPtr，然后让slow(或者fast，都一样)继续向前走slow = slow -> next；一直到slow == tempPtr; 此时经过的步数就是环上节点的个数。
2.从相遇点开始slow和fast继续按照原来的方式向前走slow = slow -> next; fast = fast -> next -> next；直到二者再次相遇，此时经过的步数就是环上节点的个数 。
4、如果存在环，求出链表的长度
思路：
1.链表长度L = 起点到入口点的距离 + 环的长度r。
2.对指针走过的节点做标记，到找到一个重复访问的节点为止，该指针走过的距离就是链表长度。
5、如果存在环，求出环上距离任意一个节点最远的点（对面节点）
思路：
对于换上任意的一个点ptr0, 我们要找到它的”对面点“，可以这样思考：同样使用上面的快慢指针的方法，让slow和fast都指向ptr0，每一步都执行与上面相同的操作（slow每次跳一步，fast每次跳两步），当fast = ptr0或者fast = prt0->next的时候slow所指向的节点就是ptr0的“对面节点”。
6、(扩展）如何判断两个无环链表是否相交，如果相交，求出第一个相交的节点
思路：
1.利用链表长度差。
2.转化为环的问题。
1.利用链表长度差。让较长的链表将它多出来的那么部分长度先走完，让后两个链表再一起往前走，知道相遇或者各自都走完。
2.转化为环的问题。我们将一个链表的头尾相连，然后从另一个链表出发判断是否有环。
原文链接: https://www.cnblogs.com/chen-cs/p/13200970.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/392255
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
