牛客算法题——链表中环的入口节点
题目描述：对于一个给定的链表，返回环的入口节点，如果没有环，返回null
扩展：你能给出不利用额外空间的解法吗？
笔者第一时间看到这个题目直接就想到了压栈，于是就用暴力解法解出来了，话不多说，直接上代码！
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
#
#
# @param head ListNode类
# @return ListNode类
#
# 额外空间的解法
class Solution:
def detectCycle(self , head ):
stack = []
pnow = head
while pnow:
if pnow in stack:
return pnow
stack.append(pnow)
pnow = pnow.next
return None
# write code here
上面的思路也很简单，就是在pnow指针不断向前搜索的时候，把所有经历的节点压入栈,如果出现重复节点入栈，那么肯定就是有环，且第一个重复的节点就是环的入口节点，直接返回当前节点即可。如果没有环，搜索到最后一个节点的next节点（空节点）之后，返回None即可。
本题目也可以利用快慢指针来解，也就是不适用额外空间的解法，思路如下。
- 快慢指针同时出发，如果快指针到达null，则说明链表没有环。
- 如果快慢指针相遇了，则说明有环。
- 在快慢指针相遇的时候，第二个慢指针从头结点出发。
- 当两个慢指针相遇的时候，相遇的位置就是环的起点。
原理：
快慢指针图示
- 假设链表有环，并且环之前的部分长n，环周长m，慢指针速度为1，快指针速度为2。环为顺时针
- 首先快指针和慢指针一起从F0S0出发。当慢指针经过n的距离到达环的起点S1的时候，快指针走过2n的距离到达F1。
- 快指针此时共走了2n的距离，在环上走了n的距离，
因此快指针此时距离环的起点n%m这么多(按顺时针计算)。
也就是说，快针要追上慢针需要多走m-n%m(即从F1顺时针回到S1的距离) - 也就是说，当快指针追上慢指针的时候，慢指针从S1走了m-n%m到达S2F2。
该点距离环的起点S1有n%m这么多距离。(快指针有多少路要追，慢指针就会从起点走多少路) - 快慢指针在S2F2相遇的时候，另一个慢指针2 从F0S0出发。
慢指针1走到S1要经过n%m。
慢指针2此时离环起点S1 n-n%m。该距离可以被m整除。
因此两个慢指针一定会在S1相遇。
class Solution:
def detectCycle(self , head ):
if not head:return None
if not head.next:return None
p_slow = head
p_slow2 = head
p_fast = head
while p_fast and p_fast.next:
p_slow = p_slow.next
p_fast = p_fast.next.next
if p_fast==p_slow:
break
if not p_fast or not p_fast.next:
return None
else:
while p_slow2 != p_slow:
p_slow2 = p_slow2.next
p_slow = p_slow.next
return p_slow2
