287. Find the Duplicate Number

本题其实也谈不上难，但是确实有一定的思维难度，需要把这道题转化为LinkedList Cycle，才容易做出。
首先谈一下为什么可以转化为LinkedList Cycle：

• 举例： [1, 3, 4, 2, 2]
• 转化为LinkedList：
  • index是value
  • value是指next
  • 有点绕，画个图表示一下：
  • 但凡有duplicate number存在，则必然有两个位置指向同一个node的情况，比如1 -> 3, 4 -> 3，这就是环的存在

这个想明白之后，余下的部分就比较简单了，就是单纯的

• 确定Cycle长度

• 找环的起点

• 时间复杂度：

• 空间复杂度：

代码如下：

class Solution {
  public int findDuplicate(int[] nums) {
    // step 1: find length of cycle, if no cycle, skip
    int len = 0;
    int slow = 0;
    int fast = 0;
    while (true) {
      fast = nums[fast];
      fast = nums[fast];
      slow = nums[slow];
      ++len;
      if (fast == slow) {
        break;
      }
    }
    // step 2
    slow = 0;
    fast = 0;
    while (len > 0) {
      fast = nums[fast];
      --len;
    }
    while (slow != fast) {
      slow = nums[slow];
      fast = nums[fast];
    }
    return slow;
  }
}