关于数据结构和算法:linear-list-链式存储方式经典问题-判定链表中有无cycle-以及-cycle-entrance-附数学推导

本文内容

快慢指针解决环形链表断定和入口寻找
快慢指针成立原理办法推导

问题形容
给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
阐明：不容许批改给定的链表。
应用 O(1) 空间解决此题(即常数内存空间)

作者：力扣 (LeetCode)
题源链接：https://leetcode-cn.com/leetb…
起源：力扣（LeetCode）
题解作者:WildDuck

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

————————————————————————————————————
原理推导

仅探讨单向链表中单个 cycle 的断定和 cycle entrance 的返回