转载 闲聊判圈算法
floyd（Floyd cycle detection）

问题：如何检测一个链表是否有环，如果有，那么如何确定环的起点？如何确定环的长度？

• 时间复杂度：O（n） （高效率）
• 空间复杂度：O（1）

此算法又成为龟兔赛跑算法，基本思想是：

好比两个人在赛跑，A的速度快，B的速度慢，经过一定时间后，A总是会和B相遇，且相遇时A跑过的总距离减去B跑过的总距离一定是圈长的n倍（初中数学题……）。

弗洛伊德（Floyd ）使用了两个指针，一个慢指针（龟）每次前进一步，快指针（兔）指针每次前进两步（两步或多步效果是等价的，只要一个比另一个快就行。但是如果移动步数增加，算法的复杂度可能增加）。如果两者在链表头以外（不包含开始情况）的某一点相遇（即相等）了，那么说明链表有环，否则，如果（快指针）到达了链表的结尾（如果存在结尾，肯定无环），那么说明没环。

环的检测从上面的解释理解起来应该没有问题。接下来我们来看一下如何确定环的起点，这也是Floyd解法的第二部分。方法是将慢指针（或快指针）移到链表起点，然后两者同时移动，每次移动一步，那么两者相遇的地方就是环的起点。

下面给出论证过程：

假设一个链表是下面这样的：

设环长为n，非环形部分长度为m，当第一次相遇时显然slow指针行走了 m+A*n+k（A表示slow行走了A圈。附：A*n 是因为如果环够大，则他们的相遇需要经过好几环才相遇）。fast行走了 m+B*n+k。

上面我们说了slow每次行走一步，fast每次行走两步，则在同一时间，fast行走的路程是slow的两倍。假设slow行走的路程为S，则fast行走的路程为2S。

用fast减去slow可得：

S=（B-A）*n

很显然这意味着当slow和fast相遇时他们走过的路程都为圈长的倍数。

接下来，将slow移动到起点位置，如下图：

然后每次两个指针都只移动一步，当slow移动了m，即到达了环的起点位置，此时fast总共移动了 2S+m。 考虑到S为环长的倍数，可以理解为：fast先从链表起点出发，经过了m到达环的起点，然后绕着环移动了几圈，最终又到达环的起点，值为2S+m。所以fast最终必定处在环的起点位置。即两者相遇点即为环的起点位置。

在LeetCode上看到一道题 #141

Given a linked list, determine if it has a cycle in it.

 Definition for singly-linked list.   
  class ListNode(object):  
     def __init__(self, x):  
         self.val = x  
         self.next = None  

如何确定链表是否有环呢？

Floyd判圈算法
假设龟兔从同一起点（链表的起始位置）出发，如果该链表有环，当兔子和乌龟均进入后，必定兔子会在领先乌龟一圈后与乌龟在链表的环中相遇。所以可以用以下代码判断链表是否有环。其中slow的起始位置为head，每次移动一步；fast的起始位置也为head，每次移动两步，当两者相遇时即说明该链表有环。

def hasCycle(self, head):
    try:
        slow = head
        fast = head.next
        while slow is not fast:
            slow = slow.next
            fast = fast.next.next
        return True
    except:
        return False

wiki上的python代码

def floyd(f, x0):
     tortoise = f(x0)       # f(x0) is the element/node next to x0.
     hare = f(f(x0))
     while tortoise != hare:
         tortoise = f(tortoise)
         hare = f(f(hare))
         if (tortoise == hare):
            return True
     return False

那么，如何判断环的长度呢？

首先要确定链表中有环。

假设环起始的位置距离链表起始距离为m，而环的长度为λ，第一次相遇点距离环的起点距离为k。则第一次相遇时乌龟走过的距离ν = m + λ * a + k， 兔子走过的距离2ν = m + λ * b + k。所以ν = (b-a) * λ 为环长度的倍数。

此时将兔子抓回起点命令其以和乌龟同样的速度行走，而乌龟则在原地继续以之前的速度行走。当兔子的行走距离为m（即走到环的起点）时，乌龟走了ν + m，而由于ν为环长度的倍数，所以此时乌龟也走在环的起点，即兔子和乌龟相遇在环的起点。

当然还有更简便的方法，当两者相遇后，命令乌龟静止不动，兔子降速为每次前进一步，当兔子再次遇见乌龟时，它比乌龟多跑的距离就是环的长度。

求环的长度

def floyd(f, x0):

    tortoise = f(x0) # f(x0) is the element/node next to x0.
    hare = f(f(x0))
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(f(hare))

    # 方法一、乌龟回到原点，兔子降速（与兔子回原点降速相同）    
    m = 0
    tortoise = x0
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)   # Hare and tortoise move at same speed
        m += 1
 
    # 方法二、乌龟静止不动，兔子降速每次前进一步
    lam = 1
    hare = f(tortoise)
    while tortoise != hare:
        hare = f(hare)
        lam += 1
 
    return lam, m

习得龟兔同跑的判圈算法后，来看一下LeetCode #202

Write an algorithm to determine if a number is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

"happy数"的含义为：将一个数字的每位平方后相加，相加后的数继续进行每位平方后相加，如此循环，当相加到最后的数字始终为1时，即为"happy数"。

Example: 19 is a happy number

1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
Python解决方案：

def digitSquareSum(n):
    sum, tmp = 0, 0
    while n:
        tmp = n % 10
        sum += tmp * tmp
        n /= 10
    return sum


def isHappy(n):
    slow = digitSquareSum(n)
    fast = digitSquareSum(digitSquareSum(n))
    while slow != fast:
        slow = digitSquareSum(slow)
        fast = digitSquareSum(digitSquareSum(fast))
    if slow == 1:
        return True
    else:
        return False

类似的还有这题leetcode287

Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:
Input: [1,3,4,2,2]
Output: 2
Example 2:
Input: [3,1,3,4,2]
Output: 3
Note:
You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n2).
There is only one duplicate number in the array, but it could be repeated more than once.

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例 1:

输入: [1,3,4,2,2]
输出: 2
示例 2:

输入: [3,1,3,4,2]
输出: 3
说明：

不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字，但它可能不止重复出现一次。

此处时间空间都做出的限制，O(1)代表不能另辟空间，因此不能用简单的方法去做，由于数组中元素大小都是正整数且都小于数组长度，因此可将数组中的每个值视为对应空间的后继索引，视为链表。

Solution：

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        tortoise = nums[0]
        hare = nums[0]
        while True:
            tortoise = nums[tortoise]
            hare = nums[nums[hare]]
            if tortoise == hare:
                break
        #进入圈中    
        #圈的起点就是答案
        ptr1 = nums[0]
        ptr2 = tortoise
        while ptr1 != ptr2:
            ptr1 = nums[ptr1]
            ptr2 = nums[ptr2]
            
        return ptr1