链表环-快慢指针的数学原理

代码示例

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null){
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while(slow != fast){
            if(fast == null || fast.next == null){
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}

原理解析

设快指针在慢指针距离1格，快指针每次移动2格，满指针每次移动1格。当两个指针都进入环后，那么移动$n$次且相遇时有：

$$此处：(2n+1)\%s=n\%s=m,s为环的长度（不是链表长度）\\ 设:2n+1=s*k_{1}+m,k_{1}\in Z\\ n=s*k_2+m,k_{2}\in Z\\ 得：n+1=s*(k_{1}-k_{2}),(k_{1},k_{2}\in Z,k_{1}>k_{2} )$$

图解

$k_{1}$与$k_{2}$取合适的整数时，此方程的n有解。故若链表中存在环，那么快慢指针必定会相遇。