提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
前言
学到老活到老
一、题目
环形链表 II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
提示
链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引
进阶
你是否可以使用 O(1) 空间解决此题？
二、思路
1.快慢指针
首先想到判断列表是否有环的重要方法就是双指针（快慢指针），只要快慢指针（一次慢指针走一步，快指针走两步）能够相遇，则一定存在环。如果快指针到了链表尾，则无环。那么为了找到入口，是否可以探寻一下其中的数学关系呢？
①第一步，我们来假设从链表的起点到环入口处的长度为a，环的一遍长度为b，那么当快慢指针相遇的时候，显然快指针一定比慢指针多走了整数个b的距离（可以想象为操场跑圈，一个b为一圈），又因为快指针的速度是慢指针的2倍，当时间相同的情况下，快指针比慢指针多跑的距离就是慢指针所跑的距离，因此，当二者相遇时，慢指针走的距离为k*b（k为正整数）
②第二步，当慢指针在有环的链表中移动，每当路程为a+k*b（k为非负整数）时，就会到达环的入口，因此，当慢指针第一次与快指针相遇时，再走a步它就会再一次路过环的入口；那么如何让他再走a步呢？让我们回到之前的设定，a是假设的链表的起点到环入口处的长度，因此，如果我们此时放一个慢指针二号在链表起点，让他和慢指针一号同时移动（一次一步），那么当两个慢指针相遇的时候，就路过了环的入口。
最后，双指针思路（准确讲是“三指针”）理论上很复杂，但实现起来却很容易：首先让快慢指针遍历链表，如果相遇失败，说明链表无环，直接返回None；如果成功相遇，再设置第二个慢指针继续遍历，返回相遇的结点即可。
2.哈希表
此外还想到一种笨方法，很猎奇（liumang）：
遍历一次链表，途中将每个结点加入哈希表中，当遇到重复结点即可找到，这种方法空间复杂度较高，尝试一下发现还真行。
就怕流氓有文化啊家人们
三、代码
1.快慢指针
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
fast=slow=slow2=head #设置快慢2指针
#第一次
while(fast != None):
slow=slow.next #移动
if(fast.next != None):
fast=fast.next.next
else:
fast=None
if(fast == slow): #相遇
break
if(fast == None): #无环
return None
#第二次
while(slow != slow2):
slow=slow.next
slow2=slow2.next
return slow
2.哈希表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
p=head #设置指针
d=dict() #创建哈希表
#第一次
while(p != None):
if(p in d): #结点在哈希表中
return p
else: #不在
d[p]=1
p=p.next
if(p==None): #无环
return None
