## Description

https://leetcode.com/problems/linked-list-cycle-ii/

Given 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. **Note that pos is not passed as a parameter**.

**Notice** that you **should not modify** the linked list.

**Example 1:**

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

**Example 2:**

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

**Example 3:**

Input:head = [1], pos = -1Output:no cycleExplanation:There is no cycle in the linked list.

**Constraints:**

- The number of the nodes in the list is in the range
`[0, 10`

.^{4}] `-10`

^{5}<= Node.val <= 10^{5}`pos`

is`-1`

or a**valid index**in the linked-list.

**Follow up:** Can you solve it using `O(1)`

(i.e. constant) memory?

## Explanation

We can have a hashmap to check whether if the node has been visited.

## Python Solution

```
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
visited = set()
while head != None:
if head in visited:
return head
visited.add(head)
head = head.next
return None
```

- Time Complexity: O(N).
- Space Complexity: O(N).