287. Find the Duplicate Number 怎么证明环的

如题，怎么可以证明他有环呢

感觉大家可以用这个解法怎么去理解呢：

1. class Solution {
   
2.     public int findDuplicate(int[] nums) {
   
3.         // Find the intersection point of the two runners.
   
4.         int tortoise = nums[0];
   
5.         int hare = nums[0];
   
6.         do {
   
7.             tortoise = nums[tortoise];
   
8.             hare = nums[nums[hare]];
   
9.         } while (tortoise != hare);
   
10. 
    
11.         // Find the "entrance" to the cycle.
    
12.         int ptr1 = nums[0];
    
13.         int ptr2 = tortoise;
    
14.         while (ptr1 != ptr2) {
    
15.             ptr1 = nums[ptr1];
    
16.             ptr2 = nums[ptr2];
    
17.         }
    
18. 
    
19.         return ptr1;
    
20.     }
    
21. }
    

复制代码

每个节点都有后继节点，于是你可以无限走下去，但是总的节点数量是有限的，于是你在某个时刻必定访问一个已经访问过的节点（i.e. 环）。

但是你并不想你的访问链就是一整个环，这意味着这个链里的每个节点恰好都只有一个前继节点。于是你从0开始，因为0没有前继节点。