在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
