leetcode 第141题 环形链表， 第142题 环形链表 II ， 第287题 寻找重复数（Python解法）
leetcode 第141题 环形链表， 第142题 环形链表 II ， 第287题 寻找重复数（Python解法）
今天的前两题是关于环形链表的，第三题是要找出数组中出现的重复数字，乍一看和前两题无关，但是最后也用到了环形链表的知识，只是这里的着手点比较隐蔽。
问题分析
141题 环形链表
先看141题，141题是给出一个链表，然后判断该链表是否是一个循环链表，如果是返回True，如果不是返回False。
这一题直接用快慢指针解题，首先快慢指针都指向头节点，然后慢节点每次都向后移一个节点，而快指针每次向后移两个节点。如果慢节点或慢节点的下个节点是否为空，如果为空，说明不是环形链表，返回False。如果不是，接着向下移动。
假如链表中存在环，由于快指针每次都比慢指针多走一倍的距离，所以最后快指针一定会将慢指针“套圈”相遇。
如第一张图所示，开始快慢指针都指向头节点，在移动后一段距离后，如第二张图所示，快指针“套圈”慢指针，再次相遇。再次相遇说明链表存在环，所以返回True。
142题 环形链表 II
142题是141题的升级，它不仅先要判断链表是否有环，还有找出环形链表的入口。
开始的处理和141题一样，先用快慢指针找出第二次相遇的节点（如果不是环形链表就返回None，不需要向下继续操作）。再次相遇后，如下图所示：
要求返回的是节点4，现在是在节点7相遇。此外，在这个图上做一点标识，节点1到节点4的距离a=3，节点4到节点7的距离为b=3。相遇时，慢节点从节点1到节点7，总共移动的距离为a+b=6，而快节点移动的距离是慢节点的两倍，为12（从1->4->7->4->7)。此外可以知道的是从节点7到节点4的距离也为a=3。
有了这些准备，下面就好办了。将其中的一个指针（这里用快指针）重新移到头节点1。这时候两个指针都同时向后移动。每次移动一个位置。
到最后，两个指针移动a的距离，重新在节点4相遇，此时只要返回节点4就OK了。
287题 寻找重复数
第287题如下，在一个包含n+1个元素的数组中找出重复的元素，其中元素的值在1~n之间。关于数组所有元素的值小于其长度时，可以使用原位改动元素值的方法，但是第一个条件就说此数组不可更改，所以此方法不可用，排序等方法也不可用；而且第二个条件为只能使用常数级空间，所以不能用集合存储元素。第三个条件是时间复杂度小于O(n2)，所以不能用暴力法来解题。
此题可以用上述的环形链表的思想巧妙的来解答。假设下面是一个待求的数组，里面的重复元素为9。
接下来将此数组看成是一个链表。根据数组的元素来构建链表，比如nums[0]=2,那么节点2指向的下一个节点就是nums[2]=9， 节点9的下一个节点是nums[9]=1，由于题目限制，是永远不会超过数组的范围的。到了节点7时，它的下一个节点为nums[7]=9，这样就形成了一个环，而且环的入口（节点9）即为重复元素。
得到的链表如下：
构造好环形链表之后，接下来就可以用142题的方法来解题了。用这种方法时间复杂度为O(n)，空间复杂度为O(1)，而且没有改变数组元素的值。
源码
141题 环形链表
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
if head:
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if fast == slow:
return True
return False
142题 环形链表 II
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNod
:rtype: ListNode
"""
fast = slow = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
fast = head
while fast != slow:
fast = fast.next
slow = slow.next
return fast
return None
287题 寻找重复数
class Solution:
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
slow = nums[nums[0]]
fast = nums[nums[nums[0]]]
while slow != fast:
slow = nums[slow]
fast = nums[nums[fast]]
slow = nums[0]
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow