自己想的时候只想到了用内存去把第一次遇到的数据存起来, 但是题目要求空间复杂度为O(1), 就去百度了一下, 看到了这种通过数学计算的方式去做这件事, 大体可以描述如下:

  1. 定义两个指针,一快一慢,快的叫fast, 慢的叫slow
  2. 慢的每次获取 slow.next 也就是前进一步
  3. 快的每次获取 fast.next.next 也就是前进两步
  4. 假设无环,任意一次前进后发现当前节点没有后续节点说明这是个无环图
  5. 假设有环, fast跑的速度快, slow速度慢, fast回先进环, 假设环有N个节点,fast在环里不断循环,slow也一定会进环
  6. fast 与 slow同时进环,且它俩可处于环内任意位置, slow每次前进一次,fast每次前进两次, 假设 N为奇数,设为3
    slow处于位置2, slow处于位置1, 下次循环slow处于位置2, fast处于1, 再次循环 fast与slow与位置3相遇,以此
    类推任意位置都会遇到, 如果N为偶数,设为4, slow处于位置1,fast处于位置2, 再次移动为 slow位置2, fast位置
    4, slow位置3, fast位置2, slow位置4,fast位置4,相遇, 其他情况全部会在slow小于位置4的时候相遇
  7. 最直接的解释为什么会相遇: 如果同时处于环内,fast比slow快1,每次行动距离会缩减一,最终会追到slow身后,并在下
    次行动后相遇