链表带环问题

在链表的学习中，我们有时候会遇到环形链表，那么环形链表是什么呢？下面由我为大家讲解！

一，什么是环形链表

哈哈哈~~其实也就是带环的链表啦~~

如图所示

又或者是这样

所以带环链表有一个特性，进入就会出不来，进入了死循环~~！

二.关于环形链表的经典问题

1.下面有一道例题

这一题的最好想象的思路便是快慢指针，那么什么是快慢指针呢？

（1）快慢指针

首先，对链表的操作基本都是靠指针去完成的，因此肯定需要一个指针去维护这个链表，但环形链表有一个很重要的特性：就是由于有环状结构，因此指针一旦进入环状，就会在一直在链表里面，永远走不出来。因此我们应该用两个指针，一个遍历速度快一点，另一个遍历速度慢一点，简称“快慢指针”。

（2）思路

引用快慢指针之后，一旦慢指针进入环，通过快慢指针的速度差，当快指针追上慢指针的时候，就代表链表是环状的，否则快指针一旦为空，就说明链表不是环状链表。

即快慢指针相遇的时候，就可以表示它们带环！

我们这边先假设快指针比慢指针多走1步，即快指针走两步，慢指针走一步~

我们这样就容易得出代码

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

三.其中存在的问题

这样就可以得出代码~~~

但是爱思考的人都会想

1. 为什么一定会相遇？有没有可能错过或者永远的追不上？

2. 满指针走1步，快指针走3步，4步，5步或者n步是否能解决问题?

下面我们先解决第一个问题~

首先我们假设slow(慢指针）进入环的时候与fast（快指针）的距离为n

这样就解决了第一个问题~！

再来第二个问题

首先fast先走3步

我们还是假设slow进入fast时距离为N（下面都是如此）

这时slow和fast的历程有着两种情况（N为奇偶，左边为偶数，右边为奇数）

这时出现追成-1的概念，那么是什么问题呢？

即错过了，进行新的一轮追击

若C-1为偶数------这样就直接追上了
若C-1为奇数------那么好像就永远追不上

问题是我们真的永远追不上嘛？

四：分析

我们先总结一下

永远追不上的条件是什么 -----》同时存在N为奇数C为偶数的时候，便永远追不上~~

我们想一下是否会真的存在这种情况，这时就需要我们的一些数学知识

首先我们先假设slow进环前走的距离为L，且slow进环时fast已经走了x圈
这时slow走的距离为L，fast走的距离为L + x*C + C-N
fast的速度时slow的三倍

这时我们可以得出两个等式

3*L =L+x*C+C-N 2*L=(x+1)*C-N

偶数=(x+1)*偶数-奇数，我们会发现这个表达式并不会存在，偶数减去奇数必然不会为偶数

只有奇数减奇数才能等于偶数--》（x+1）*偶数一定为偶数

反证N为奇数且C为偶数的情况不能同时存在，永远追不上的条件不存在（所以我们还是可以追上滴）

五.结论

N若为偶数第一轮就追上了。

N若为奇数第一轮追不上，C-1是偶数时第二轮就追上了~

ps.上面只说了走3步的情况，还有走4步，5步或n步的情况都与三步相似都是可以追上的~只不过是多走的趟数！

六. 环形链表另一个问题

1.如何找到环形链表的入口节点

(1) 问题描述

简单来说就是这里

（2）思路

这里我们通过环形链表可以得出一些结论：

这里我们设起点到入口的距离是 L；入口到相遇点的距离为 X；链表的环型部分为 C；快指针速度为 2；慢指针速度为 1.

因此慢指针走的路程为：L+X。

到了这里，你或许就会问，为什么慢指针一定会在一圈内被快指针追上呢？

假设最坏的情况（即快慢指针最远的相对距离）为在慢指针刚到入口时快指针在它的前面，那么距离为 C - 1。因为这两个指针的相对速度为1，因此总共要移动（C - 1）/ 1 次，因此慢指针的移动距离为：1 *（（C - 1）/ 1）< C。

言归正传，快指针走的路程为：n*C+X+L。

因此便有了如下等式：2（L + X）= n * C + X + L;

化简后就是这个结论：L=n*C-X.

(3) L = n * C - X

这个式子是什么意思呢？其实就是说在相同的时间内，慢指针从起点走到入口时，快指针从相遇点（X处）开始走 n 圈，最后与慢指针相遇，且此时新的相遇点恰好是环形链表的入口处！！！

(4)代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* detectCycle(struct ListNode* head) {
    struct ListNode *slow = head, *fast = head;
    while (fast != NULL) {
        slow = slow->next;
        if (fast->next == NULL) {
            return NULL;
        }
        fast = fast->next->next;
        if (fast == slow) {
            struct ListNode* ptr = head;
            while (ptr != slow) {
                ptr = ptr->next;
                slow = slow->next;
            }
            return ptr;
        }
    }
    return NULL;
}