[link](https://leetcode.com/problems/linked-list-cycle-ii/)

---

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 = [1], 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?

---

The method uses two pointers, slow and fast, to traverse the linked list. Both pointers are initially set to the head of the linked list.

The method then enters a while loop with two conditions: fast and fast.next should not be None (i.e., there are at least two nodes remaining in the linked list). The fast pointer moves two steps ahead, while the slow pointer moves one step ahead in each iteration.

Inside the loop, the method checks if the slow pointer is equal to the fast pointer. If they are equal, it means the linked list has a cycle, and the loop is broken.

After breaking the loop, the method checks if either fast or fast.next is None. If either of them is None, it means the linked list is acyclic, and the method returns None.

If the linked list contains a cycle, the method resets the slow pointer to the head of the linked list and enters a new loop. In this loop, both slow and slow2 pointers move one step at a time until they meet. The meeting point is the node where the cycle begins.

Finally, the method returns the slow2 pointer, which points to the node where the cycle begins.

#### Solution 1

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow, fast = head, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if slow == fast:
                break
        
        if not fast or not fast.next:
            return None

        slow2 = head
        while not slow2 == slow:
            slow2 = slow2.next
            slow = slow.next
        
        return slow2

O(T): O(n)
O(S): O(1)