Give you a list of the head node head , Judge whether there are links in the list .
If there is a node in the linked list , It can be done by continuously tracking next The pointer reaches again , Then there is a ring in the linked list . To represent a ring in a given list , The evaluation system uses an integer pos To indicate where the end of the list is connected to the list （ Index from 0 Start ）. Be careful ：pos Not passed as an argument . Just to identify the actual situation of the linked list .
If there are rings in the list , Then return to true . otherwise , return false .
Example 1：
Input ：head = [3,2,0,-4], pos = 1
Output ：true
explain ： There is a link in the list , Its tail is connected to the second node .
Example 2:
Input ：head = [1,2], pos = 0
Output ：true
explain ： There is a link in the list , Its tail is connected to the first node .
Example 3：
Input ：head = [1], pos = -1
Output ：false
explain ： There are no links in the list .
Is there any pos This condition does not affect the question , To judge whether there are links in a linked list, we usually use Floyd Algorithm , That is, the form of double pointer , Set up a fast pointer and a slow pointer .
If there are links in the linked list , Suppose two students are running on the playground , Two men start at the same time , One runs fast and the other runs slowly , Suppose two students have been running , Those who are so fast will surpass those who are slow , And at some point, I will meet the slow students .
Set the starting position of the pointer to head, Set the step size of fast pointer and slow pointer （ It is usually set as 1 and 2）, If there are rings , Then the fast pointer and the slow pointer will coincide .
The next step is to make it clear that there is no ring , When there is only one node , The next node of the fast pointer is None; The next node of the next node of the fast node is None（ In steps of 2）, It also means that there is no ring .
## python3
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def hasCycle(self, head: [ListNode]) -> bool:
if head == None:
return False
slow = head
fast = head
while fast.next != None and fast.next.next != None:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
Given the head node of a linked list head , Return to the first node of the link where the list begins to enter . If the list has no links , Then return to null.
If there is a node in the linked list , It can be done by continuously tracking next The pointer reaches again , Then there is a ring in the linked list . To represent a ring in a given list , The evaluation system uses an integer pos To indicate where the end of the list is connected to the list （ Index from 0 Start ）. If pos yes -1, There are no links in the list . Be careful ：pos Not passed as an argument , Just to identify the actual situation of the linked list .
No modification allowed Linked list .
Example 1:
Input ：head = [3,2,0,-4], pos = 1
Output ： The return index is 1 The linked list node of
explain ： There is a link in the list , Its tail is connected to the second node .
Example 2:
Input ：head = [1,2], pos = 0
Output ： The return index is 0 The linked list node of
explain ： There is a link in the list , Its tail is connected to the first node .
Example 3:
Input ：head = [1], pos = -1
Output ： return null
explain ： There are no links in the list .
Let's start with a derivation , Let's say there are a+b Nodes , Where the ring has b individual
f The number of steps is s Twice as many , be f = 2s
When they met f Than s Take a few more turns ,f = s + nb
From the above formula ,s = nb , f = 2nb
When the two meet , I put s Get to the beginning , then f and s The steps of all become 1, What would happen if the two met again ？
When s Be taken to the beginning to make ,s = 0,f = 2nb
The two meet only in the circle , hypothesis s Just inside the circle , that s = a,f = a + 2nb
because 2nb Is an integral multiple of the number of turns , So just at the beginning of the circle （2nb Can be removed ）, So at this time ,s = a,f = a, The two will just meet at the beginning , Then move together .
---------
Conclusion ：
Judge whether there is a ring by whether the fast and slow pointers can meet , If the two meet , Will slow down （ fast ） The pointer gets to the beginning , The combination of the two is 1 Move... For step size , It must be at the beginning of the ring that we meet again .
## python3
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
if head == None
return None
slow = head
fast = head
loop = False
while fast.next != None and fast.next.next != None:
slow = slow.next
fast = fast.next.next
if slow == fast:
loop = True
break
if loop:
slow = head
while slow != fast:
fast = fast.next
slow = slow.next
return slow
return None
