关于链表带环问题为什么要用快慢指针

判断链表是否带环

题目描述

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。
在这里插入图片描述
这道题我们一般想到的就是用快慢指针来解决这道题首先设置两个指针fast和slow都从头开始，fast指针一次走两步，slow指针一次走一步，当这两个指针重回在一起的时候就是带环链表，如果没有重回就是不带环链表，代码也是非常简单的，下面是代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode listnode;
bool hasCycle(struct ListNode *head) {
listnode* fast = head;
listnode* slow = head;
if(head == NULL)
{
    return false;
}
while(fast && fast->next)
{
  fast = fast->next->next;
  slow = slow->next;
  if(slow == fast)
  {
    return true;
  }

}
 return false;
}

为什么要用快慢指针

我们可以先画一个图来看看，我们先创建一个带环链表
在这里插入图片描述
下面是指针走的过程

可以发现最终两个指针相遇了，并且当slow指针进环之后，fast与slow的距离每次在缩小一位，假设他们的距离是X，每走一步就是x-1,x-2最后一直到2，1，0所以他们两个会相遇，那么我们想个问题，如果快指针每次走3步，或者走4步呢，他们两个会不会相遇？
我们就拿走3步来说说，链表的长度为y我们假设长度为11,假设快指针和慢指针之间的距离长度为X，我们假设一个是7 ，快指针每次走3步，他们之间的距离就减去3，变成4，4在减去3，变成1，然后又减3变成-2，变成负数之后就相当于开始新一轮的追击了两个指针之间的距离就是,链表长度y-2就是9，9一直减去3就变成0，他们两个指针还是追上了。
如果他们两个之间的距离是8呢，画图来看看。
在这里插入图片描述
可以发现他们两个还是追上了
通过上面的分析，我们可以总结一下X是偶数，快指针每次走三步，他们两个的距离就缩小2，变成x-2,x-4,…4,2,0就追上了，如果x是奇数那么,x-2,x-4…3,1,-1当到-1时他们又开始新一轮的追击然后他们之间的距离就变成链表长度-1变成10，是偶数，最终偶数-2就会变成0，他们两个追上了。
这里我们得到两个结论
如果
1.两个指针之间的距离x是偶数那么第一轮就追的上
2.如果两个指针之间的距离是奇数第一轮追击追不上，变成链表长度-1，进入下一轮追击，如果是偶数就追上了，如果是奇数就追不上
如果是奇数，奇数减去偶数就永远不可能等于0
如果要永远追不上，那么就必须满足下面的条件
1.两指针之间的距离是奇数
2.链表长度是偶数
这两个条件会存在吗,画图来看看
我们可以试着推导一个公式出来看看
在这里插入图片描述
当入环的时候
slow走的距离是L
fast走的距离是L+XC+(C-N),(XC代表fast走的链表的环数，有可能这个链表环很小)
fast走的距离是slow的三倍
3L = L+XC+(C-N);
化简之后就变成2L = XC+C-N
提取公因式变成
2L = C(X+1)-N;
2L肯定是偶数，因为2是偶数偶数乘偶数一定是偶数。
如果要满足这个等式那么右边的等式的结果一定要是偶数
我们把上面的这个条件带入这个公式
1.两指针之间的距离是奇数
2.链表长度是偶数
2L(偶数) = C（偶数)*(X+1)-N(奇数）；
我们可以发现这个等式不可能成立，奇数乘以偶数一定是奇数
所以这个条件不存在！
N是偶数第一轮就追上了，
N是奇数第一轮追不上，第二轮就追上了。
我们在来看一道题

环形链表II

环形链表II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改链表。

在这里插入图片描述
这是代码

typedef struct ListNode listnode;
struct ListNode *detectCycle(struct ListNode *head) {
    if(head == NULL)
    {
        return NULL;
    }
    listnode* slow = head;
    listnode* fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
        {
            listnode* meet = slow;
            while(meet!= head)
            {
              meet = meet->next;
              head = head->next;
            }
          return meet;
        }
    }
    return NULL;
}

关于这个当slow == fast的时候把slow赋值给meet，然后让head从头开始走，当遇到meet的时候就是链表环的入口这个问题，我们也可以分析一下把他写一个等式过来
根据上面的分析
我们得到
slow走的距离是L+N
fast走的距离是L+X*C+N
在这里插入图片描述
相遇时
fast走的距离是slow的两倍
我们可以得到2（L+N） = L+XC+N；
我们化简一下
L+N = XC;
L = XC-N.
通过这个等式我们可以看到L就等于fast走的链表的圈数，减去slow进环与fast相遇走的距离，圈数减去N之后就是C-N（圈数是大于等于1的整数）其实我们除开xc就是L = C-N；
那就可以得出一个结论当slow和fast相遇时，剩下的距离就等于从链表开头到链表入环的那个距离
所以就可以设一个meet和head同时往后走当他们两个相遇时就是链表的入环口。
所以就可以用这个方法解决问题。