LeetCode - 141. 环形链表 （C语言，快慢指针，配图）_141. 环形链表 c

目录

1. 什么是快慢指针

2. 非环形链表

3.代码展示

4.扩展：fast走3步，slow走一步呢？

---

1. 什么是快慢指针

        这里我们我们将介绍环形链表的经典解法——快慢指针，简单理解，指针移动快的叫做快指针fast，移动速度慢的叫慢指针slow。一般我们设快指针走两步，慢指针走一步。

        如果你对快慢指针理解或应用不太了解，可以参照下面几篇文章，去力扣练习。

LeetCode - 26. 删除有序数组中的重复项 （C语言，快慢指针，配图）-CSDN博客

LeetCode - 27. 移除元素 （C语言，快慢指针，配图）-CSDN博客

        通过下图，我们可以清晰地知道，当fast走两步，slow走一步时，如果这是一个环形链表，那么它们总有一天会遇见。

2. 非环形链表

          那么我们来看一下非环形链表长什么样，通过下面这幅图片，我们可以知道非环形链表，那么fast或fast->next 一定为空，这与元素个数有关。

        当然这也是一道经典的链表中间节点的题目：876. 链表的中间结点 - 力扣（LeetCode）

3.代码展示

        通过上面两个铺垫，我们知道了 1.怎么判断是否为环形链表，2.非环形链表的结束条件

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

4.扩展：fast走3步，slow走一步呢？

        这里我们先给出结论，不论fast走几步，slow走几步，如果是环形链表，那么它们一定会相遇。这真是令人感动。

总结一下：

1. 如果N是偶数，第一轮就相遇

2. 如果N是奇数，C是奇数，第一轮错过，第二轮就能相遇

3. 如果N是奇数，C是偶数，永远追不上（但这里的条件永远不能成立，可以自己代入上面fast走3步，slow走1步公式： 2L = n * C - N）