快慢指针找环的入口，Floyd算法推导_floyd入环点推导 知乎

如何判断链表中是否有环，并找到环的入口，这就需要使用快慢指针算法，也就是Floyd算法。

算法步骤很简单：

1. 快指针（每次两步）和慢指针（每次一步）同时从链表头开始遍历链表，直到它们在某个节点相遇。

2. 令慢指针从相遇节点出发，同时令快指针回到链表头，接着让两个指针以相同的速度前进，当它们再次相遇时，相遇的节点就是环的入口节点。

Python 代码示例：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
      
  
def hasCycle(head: ListNode) -> bool:
    slow = head
    fast = head
 
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
 
        if slow == fast:
            return True
 
    return False
 
def find_loop_start(head):
    # 设置快慢指针
    fast, slow = head, head
    
    # 让快慢指针相遇
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
        if fast == slow:  # 相遇时，说明链表存在环
            break
    
    # 如果快指针为空，则说明链表不存在环
    if not fast or not fast.next:
        return None
    
    # 将快指针重新移动到起点，慢指针不动
    fast = head
    
    # 快慢指针每次移动一个节点，相遇的节点就是环的入口
    while fast != slow:
        fast = fast.next
        slow = slow.next
    
    return fast  # 返回环的入口节点
 
 
# 创建链表
node0 = ListNode(0)
node1 = ListNode(3)
node2 = ListNode(2)
node3 = ListNode(0)
node4 = ListNode(-4)
 
node0.next = node1
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node2
 
# 检查是否有环
has_cycle = hasCycle(node0)
print("是否有环: ", has_cycle) # True
floop_start = find_loop_start(node0)

但是为什么这个算法可以找到环的入口呢？

首先，只要他们相遇点部位空就能证明链表有环，这一点很好理解，因为只有有环，快慢指针才能在不在链表为尾部相遇。并且，他们也一定会相遇，就像是跑步，慢的一定会被快的追上。

但是为什么从相遇点之后，重置指针就可以找到环的入口呢？下面进行推导：

首先，我们假定快指针都过的距离为a, 慢指针走过的距离为b, 从链表头到环入口的距离为c, 相遇的位置离按照指针绕环的方向距离环入口为d， 环的周长为r。

慢指针一定没有走完过一圈。因为快慢指针在圈内最远的距离为r-1，此时慢指针刚好进入环，快指针刚好在慢指针前面,即在圈内快指针要比慢指针夺走r-1才能追上，假设慢指针走了x,快指针走了y，则有：

y = 2x, y - x = r - 1, 2x - x = r-1 , x = r-1 ,此时慢指针走了r-1，没有走完一圈。

很明显的有如下关系：

1. 快指针走过的距离是慢指针的两倍

2. 快指针比慢指针多绕了n次环(想象跑步套圈，跑的快的肯定比跑的慢的多跑了n圈)

3. 慢指针的距离+ d 则能走完当前的环,即正好走到入口处

由1得：
a = 2b
由2得：
a - b = nr
2b -b = nr
b = nr
则由3得
b + d = c + r
b = c + r - d 
nr = r + c - d
c = (n-1)r + d

由上面式子的出当快指针从头走到环入口处时，即走了c的距离。此时慢指针刚好在从相遇点开始绕了(n-1)次环，并且又走了d的距离，也就是也到了环的入口处。则他们再次相遇的点就是环的入口。