链表环结构存在性证明与 Floyd 算法解析

链表环结构

前言

在这篇博客中，我们将深入探讨链表环结构的检测方法：

• Floyd 算法的原理：如何通过快慢指针检测环？
• 环入口的定位：如何找到环的起点？
• 通过这篇博客，我会对链表中的环结构进行相关证明解释，总结学习。

1. 环形链表（基础）

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

题目描述：

代码实现：

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

代码解释：

这个题目的实现逻辑比较简单，我们定义快慢指针来进行实现，fast 指针每次走 2 步，slow 指针每次走 1 步，当快指针和慢指针相遇的时候，如果链表中存在环，则返回 true。否则，返回 false。

2. 环形链表Ⅱ（中等）

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

题目描述：