# 142. Linked List Cycle II

2022-05-15 07:49:20

Medium

Given the `head` of a linked list, return the node where the cycle begins. If there is no cycle, return `null`.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the `next` pointer. Internally, `pos` is used to denote the index of the node that tail's `next` pointer is connected to (0-indexed). It is `-1` if there is no cycle. Note that `pos` is not passed as a parameter.

Do not modify the linked list.

Example 1: ```Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.
```

Example 2: ```Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.
```

Example 3: ```Input: head = , pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.
```

Constraints:

• The number of the nodes in the list is in the range `[0, 104]`.
• `-105 <= Node.val <= 105`
• `pos` is `-1` or a valid index in the linked-list.

Follow up: Can you solve it using `O(1)` (i.e. constant) memory?

``````# 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]:
"""
Their thinking （ Others' ）：
For the problem of finding loop in linked list , There is a general solution —— Speed pointer （Floyd  Circle method ）. Given two pointers ,
Named as  slow  and  fast, The starting position is at the beginning of the list . Every time  fast  Two steps forward ,slow  Take a step forward . If  fast
You can go to the end , So there's no loop ; If  fast  You can go on forever , So there must be a loop , And must exist
In a moment  slow  and  fast  meet . When  slow  and  fast  The first time I met , We will  fast  Move back to the beginning of the list , and
Give Way  slow  and  fast  One step at a time . When  slow  and  fast  The second time we met , The node that meets is the starting point of the loop .
"""
cycle = False
while fast:
slow = slow.next
fast = fast.next
if fast is None:
return None
if not cycle:
fast = fast.next
if slow == fast:
if cycle or fast == head:
#  Second touch or already at the beginning
return slow
cycle = True