给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：no cycle
解释：链表中没有环。
- show the code:
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
### code1
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
dic = {None}
while head:
if head not in dic:
dic.add(head)
head = head.next
else:
return head
### code2
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head:
return head
slow,quick = head,head
iscycle = False
while quick.next and quick.next.next:
slow = slow.next
quick = quick.next.next
if quick == slow:
iscycle = True
break
if iscycle:
pointer1 = head
pointer2 = slow
while pointer1 != pointer2:
pointer1 = pointer1.next
pointer2 = pointer2.next
return pointer1
else:
return None
- 此题是上一题环形链表的进阶版
- 首先代码一是常规方法哈希法，返回第一个重复出现的节点即可。
- 代码二的方法则比较有难度，其是根据一个规律：快慢指针同时从头节点出发，若链表有环，则一定会相遇，记录下这个相遇的节点，重新放一个指针在此节点上，一个指针在头节点，两者每次向前移动一步，则他们俩一定会在环的入口相遇。
- 因此代码二分为两个步骤：第一步找出链表中快慢指针相遇的节点，同时也判断了链表中是否有环，这里与上一题不同的是快慢指针的起点是相同的。第二步则重新定位两个指针，一个在上一步得到的相遇点处，一个在头节点处，两指针保持一样的速度，他们相遇的节点则是我们的结果。
-
有关上面代码二算法证明在官方题解里有详细说明：
