环形链表的判断思路

本篇文章以一道题为例子来探究单链表的带环问题

题目链接：https://leetcode.cn/problems/linked-list-cycle-ii/

题目描述： 

1.首先是如何判断链表有没有环：

思路：

1.定义快慢指针指向头节点，快指针一次走2步，慢指针一次走1步
2.在慢指针进环的那一刻，快指针在环中的某一个位置
3.快慢指针的距离每次都会减少一步，这样两个指针最终会在环中某一点相遇

如果链表不带环，那么两个指针永远都不会相遇

继续思考：

如果快指针一次走3步，慢指针一次走1步呢？两个指针最终会相遇吗？

两种情况：

1.慢指针进环时与快指针相差的节点数为偶数

2.慢指针进环时与快指针相差的节点数为奇数

 

每次两个指针步数差值减少2，那么当两指针距离为偶数时，最终就会相遇

当两指针距离为奇数时，第一次追及过程中就会错过，快指针就会比慢指针快一步，此时需要知道环的节点个数：

如果环的节点个数为奇数个，那么两指针的距离则为 奇数 - 1 个，为偶数，最终可以相遇

如果环的节点个数为偶数个，那么两指针的距离则为 偶数 - 1 个，为奇数，最终不能相遇，并且始终都会错过 

继续思考：

如果慢指针一次走1步，快指针一次走4步呢？结果又会怎样？

其实只要满足下面这个公式就可以了：

 

那么解决了链表是否带环的问题，就要去找到入环的第一个节点了

可以将其转化为一个数学问题

以快指针一次走2步，慢指针一次走1步为例

假设头节点到入环的第一个节点距离为L

入环第一个节点到相遇点的距离尾X

环的长度为C

如图，就可以列出如下式子，并最终化简

其中n为整数，并且n>=1

所以找到相遇点后，让一个指针meet指向相遇点，让一个指针cur指向头节点，两个指针同时往后走，最终再次相遇的点则为入环的第一个节点

代码如下：

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* slow, * fast;
    slow = fast = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        // 判断是否为环形链表
        if (slow == fast)
        {
            struct ListNode* meet = slow;
            // 走到入环的第一个节点
            while (meet != head)
            {
                meet = meet->next;
                head = head->next;
            }
            return meet;
        }
    }
    return NULL;
}