摘要：由于要比移动的快，如果有环，一定会先进入环，而后进入环。现在问题就简单了，由于移动的距离永远是的一般，因此当遍历玩整个环长度个节点的时候正好遍历了个节点，也就是说，此时正好指向距离最远的点。
首先，关于单链表中的环，一般涉及到以下问题：
1.给一个单链表，判断其中是否有环的存在；
2.如果存在环，找出环的入口点；
3.如果存在环，求出环上节点的个数；
4.如果存在环，求出链表的长度；
5.如果存在环，求出环上距离任意一个节点最远的点（对面节点）；
6.（扩展）如何判断两个无环链表是否相交；
7.（扩展）如果相交，求出第一个相交的节点；
下面，我将针对上面这七个问题一一给出解释和相应的代码。
1.判断时候有环（链表头指针为head）
对于这个问题我们可以采用“快慢指针”的方法。就是有两个指针fast和slow，开始的时候两个指针都指向链表头head，然后在每一步
操作中slow向前走一步即：slow = slow->next，而fast每一步向前两步即：fast = fast->next->next。
由于fast要比slow移动的快，如果有环，fast一定会先进入环，而slow后进入环。当两个指针都进入环之后，经过一定步的操作之后
二者一定能够在环上相遇，并且此时slow还没有绕环一圈，也就是说一定是在slow走完第一圈之前相遇。证明可以看下图：
当slow刚进入环时每个指针可能处于上面的情况，接下来slow和fast分别向前走即：
if (slow != NULL && fast->next != NULL)
{
slow = slow -> next ;
fast = fast -> next -> next ;
}
也就是说，slow每次向前走一步，fast向前追了两步，因此每一步操作后fast到slow的距离缩短了1步，这样继续下去就会使得
两者之间的距离逐渐缩小：...、5、4、3、2、1、0 -> 相遇。又因为在同一个环中fast和slow之间的距离不会大于换的长度，因此
到二者相遇的时候slow一定还没有走完一周（或者正好走完以后，这种情况出现在开始的时候fast和slow都在环的入口处）。
问题1是否存在环的解答
typedef struct node{
char data ;
node * next ;
}Node;
bool exitLoop(Node *head)
{
Node *fast, *slow ;
slow = fast = head ;
while (slow != NULL && fast -> next != NULL)
{
slow = slow -> next ;
fast = fast -> next -> next ;
if (slow == fast)
return true ;
}
return false ;
}
问题2 环的入口点：
从上面的分析知道，当fast和slow相遇时，slow还没有走完链表，假设fast已经在环内循环了n(1<= n)圈。假设slow走了s步，则fast走了2s步，又由于
fast走过的步数 = s + n*r（s + 在环上多走的n圈），则有下面的等式：
2s = s + n r；（1）
=> s = n*r；（2）
如果假设整个链表的长度是L，入口和相遇点的距离是x（如上图所示），起点到入口点的距离是a(如上图所示)，则有：
a + x = s = n * r; (3) 由（2）推出
a + x = (n - 1) r + r = (n - 1) r + (L - a) (4) 由环的长度 = 链表总长度 - 起点到入口点的距离求出
a = (n - 1) * r + (L -a -x) (5)
从式子（5）以及上图我们可以看出，从链表起点head开始到入口点的距离a,与从slow和fast的相遇点（如图）到入口点的距离相等。
因此我们就可以分别用一个指针（ptr1, prt2），同时从head与slow和fast的相遇点出发，每一次操作走一步，直到ptr1 == ptr2，此时的位置也就是入口点！
到此第二个问题也已经解决。
Node* findLoopStart(Node *head)
{
Node *fast, *slow ;
slow = fast = head ;
while (slow != NULL && fast -> next != NULL)
{
slow = slow -> next ;
fast = fast -> next -> next ;
if (slow == fast) break ;
}
if (slow == NULL || fast -> next == NULL) return NULL ; //没有环，返回NULL值
Node * ptr1 = head ; //链表开始点
Node * ptr2 = slow ; //相遇点
while (ptr1 != ptr2)
{
ptr1 = ptr1 -> next ;
ptr2 = ptr2 -> next ;
}
return ptr1 ; //找到入口点
第3个问题，如果存在环，求环上节点的个数：
方式1：记录下相遇节点存入临时变量tempPtr，然后让slow(或者fast，都一样)继续向前走slow = slow -> next；一直到slow == tempPtr; 此时经过的步数就是环上节点的个数；
方式2： 从相遇点开始slow和fast继续按照原来的方式向前走slow = slow -> next; fast = fast -> next -> next；直到二者再次项目，此时经过的步数就是环上节点的个数 。
两种方式本质是一样的都是在相遇点再次开始走一遍直到再次相遇。
问题4是如果存在环，求出链表的长度：
问题二已经知道了起点到入口点的距离，问题三知道了环的长度r；
链表长度L = 起点到入口点的距离 + 环的长度r;
问题5是，求出环上距离任意一个节点最远的点（对面节点）
如下图所示，点1和4、点2和5、点3和6分别互为”对面节点“ ，也就是换上最远的点，我们的要求是怎么求出换上任意一个点的最远点。
对于换上任意的一个点ptr0, 我们要找到它的”对面点“，可以这样思考：同样使用上面的快慢指针的方法，让slow和fast都指向ptr0，每一步都执行与上面相同的操作（slow每次跳一步，fast每次跳两步），
当fast = ptr0或者fast = prt0->next的时候slow所指向的节点就是ptr0的”对面节点“。
如上图，我们想像一下，把环从ptro处展开，展开后可以是无限长的（如上在6后重复前面的内容）如上图。
现在问题就简单了，由于slow移动的距离永远是fast的一般，因此当fast遍历玩整个环长度r个节点的时候slow正好遍历了r/2个节点，
也就是说，此时正好指向距离ptr0最远的点。
转载原文：https://blog.csdn.net/doufei_...
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/31653.html
摘要：前言本章将分享十一道来自牛客网中的经典链表算法题来介绍数据结构中链表在算法题中的应用。注意，函数返回结果后，链表必须保持其原始结构。 前言：本章将分享十一道来自Le...
摘要：既然说到地址空间了就顺带说一下上面环形链表这道题的另一种很的解法吧。介绍完常规操作链表的一些基本知识点后，现在回到快慢指针。 前几天第一次在 Segmentfault 发文—JavaScript：十大排序的算法思路和代码实现，发现大家似乎挺喜欢算法的，所以今天再分享一篇前两个星期写的 Leetcode 刷题总结，希望对大家能有所帮助。 本文首发于我的blog 前言 今天终于...
摘要：链式存储结构的线性表将采用一组任意的存储单元存放线性表中的数据元素。三单向链表的实现下面的程序分别实现了线性表的初始化获取线性表长度获取指定索引处元素根据值查找插入删除清空等操作。 文章有不当之处，欢迎指正，如果喜欢微信阅读，你也可以关注我的微信公众号：好好学java，获取优质学习资源。 一、概述 单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读...
摘要：同时让当前结点的指针指向，从而实现从链表尾部开始的局部反转当递归函数全部出栈后，链表反转完成。这个链表的倒数第个节点是值为的节点。新链表是通过拼接给定的两个链表的所有节点组成的。 目录 1.反转链表 K个一组翻转链表 链表的中间节点： 链表倒数第k个节点： 删除链表倒数第k个节...
阅读 2251·2021-11-19 09:40
阅读 3398·2021-10-12 10:12
阅读 1683·2021-09-22 15:04
阅读 2799·2021-09-02 09:53
阅读 653·2019-08-29 11:03
阅读 1027·2019-08-28 18:11
阅读 1529·2019-08-23 15:28
阅读 3456·2019-08-23 15:05
