# Linked List Cycle II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/linked-list-cycle-ii)
Canonical: https://scaleengineer.com/dsa/problems/linked-list-cycle-ii
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Hash Table, Linked List
**Companies:** [Paytm](https://scaleengineer.com/companies/paytm), [TikTok](https://scaleengineer.com/companies/tiktok), [Ripple](https://scaleengineer.com/companies/ripple)
---
## Problem
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:**

![](https://assets.glich.co/dsa/linked-list-cycle-ii/image0.png) 

**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:**

![](https://assets.glich.co/dsa/linked-list-cycle-ii/image1.png) 

**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:**

![](https://assets.glich.co/dsa/linked-list-cycle-ii/image2.png) 

**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?

# Approaches
## Hash Set Approach
This approach involves iterating through the linked list and storing each visited node in a hash set. If we encounter a node that is already in the set, we have found the starting point of the cycle.
**Time:** O(N) · **Space:** O(N)
**Pros:** Simple and intuitive to understand and implement.; Guaranteed to find the cycle start if one exists.
**Cons:** Requires extra space to store visited nodes, which can be up to the size of the list.; Does not meet the O(1) space complexity follow-up requirement.
### Explanation
We can solve this problem by using a hash set to keep track of the nodes we have already visited.
1.  Initialize an empty `HashSet` to store `ListNode` objects.
2.  Start traversing the list from the `head` node with a pointer, let's call it `current`.
3.  In each step of the traversal, check if the `current` node is already present in the hash set.
4.  If the hash set already contains the `current` node, it means we have visited this node before, and it is the first node of the cycle. We return this `current` node.
5.  If the `current` node is not in the hash set, we add it to the set and move to the next node (`current = current.next`).
6.  If we reach the end of the list (`current` becomes `null`), it signifies that there is no cycle. In this case, we return `null`.
```java
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        Set<ListNode> visited = new HashSet<>();
        ListNode current = head;
        while (current != null) {
            if (visited.contains(current)) {
                return current;
            }
            visited.add(current);
            current = current.next;
        }
        return null;
    }
}
```
### Algorithm
- Create an empty `HashSet<ListNode>` called `visited`.
- Initialize a pointer `current = head`.
- Loop while `current` is not `null`:
  - If `visited` contains `current`, then a cycle is detected. Return `current` as it's the start of the cycle.
  - Add `current` to the `visited` set.
  - Move to the next node: `current = current.next`.
- If the loop completes, it means no cycle was found. Return `null`.

## Floyd's Tortoise and Hare Algorithm
This is an optimal, two-pointer approach that solves the problem in constant space. It consists of two phases: first, detecting if a cycle exists, and second, finding the exact node where the cycle begins.
**Time:** O(N) · **Space:** O(1)
**Pros:** Extremely efficient in terms of memory, using only O(1) extra space.; Time complexity is linear, O(N).; Does not modify the linked list.
**Cons:** The logic, particularly for finding the start node, is more complex and less intuitive than the hash set method.
### Explanation
This classic algorithm, also known as the two-pointer algorithm, elegantly solves the problem without using extra space.

**Phase 1: Cycle Detection**
We use two pointers, `slow` and `fast`. The `slow` pointer moves one step at a time, while the `fast` pointer moves two steps at a time.
- If the list has no cycle, the `fast` pointer (or `fast.next`) will eventually become `null`.
- If there is a cycle, the `fast` pointer will eventually enter the cycle and lap the `slow` pointer. They are guaranteed to meet at some node within the cycle.

**Phase 2: Finding the Cycle's Start Node**
Once `slow` and `fast` meet, we can find the start of the cycle. Let's analyze the distances:
- Let `L` be the distance from the `head` to the cycle's start node.
- Let `C` be the length of the cycle.
- Let `k` be the distance from the cycle's start node to the meeting point.

When they meet:
- Distance traveled by `slow` = `L + k`
- Distance traveled by `fast` = `L + k + n*C` (for some integer `n >= 1`)

Since `fast` moves twice as fast as `slow`:
`2 * (L + k) = L + k + n*C`
`2L + 2k = L + k + n*C`
`L + k = n*C`
`L = n*C - k`

This equation tells us that the distance from the head to the cycle start (`L`) is equal to `n` full cycles minus `k`. This implies that if we start one pointer from the `head` and another from the meeting point, and move them one step at a time, they will meet at the cycle's start node.
- A pointer starting at `head` will travel `L` steps to reach the start.
- A pointer starting at the meeting point (which is `k` steps into the cycle) needs to travel `C - k` steps to reach the start. The equation `L = n*C - k` can be rewritten as `L = (n-1)C + (C-k)`. This confirms that after `L` steps, the pointer from the meeting point will also be at the cycle start.

So, after the meeting, we reset one pointer to the `head` and keep the other at the meeting point. Then we advance both one step at a time until they meet again. This new meeting point is the start of the cycle.

```java
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }

        ListNode slow = head;
        ListNode fast = head;
        boolean hasCycle = false;

        // Phase 1: Detect if a cycle exists
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                hasCycle = true;
                break;
            }
        }

        if (!hasCycle) {
            return null;
        }

        // Phase 2: Find the start of the cycle
        ListNode ptr1 = head;
        ListNode ptr2 = slow; // or fast, as they are at the same meeting point
        while (ptr1 != ptr2) {
            ptr1 = ptr1.next;
            ptr2 = ptr2.next;
        }

        return ptr1;
    }
}
```
### Algorithm
- Initialize two pointers, `slow` and `fast`, both to `head`.
- **Phase 1: Detect Cycle**
  - Loop as long as `fast` and `fast.next` are not `null`.
    - Move `slow` one step: `slow = slow.next`.
    - Move `fast` two steps: `fast = fast.next.next`.
    - If `slow` and `fast` meet (`slow == fast`), a cycle is detected. Break the loop and proceed to Phase 2.
- If the loop finishes without the pointers meeting, there is no cycle. Return `null`.
- **Phase 2: Find Cycle Start**
  - Reset one pointer to the beginning of the list: `ptr1 = head`.
  - Keep the other pointer at the meeting point: `ptr2 = slow`.
  - Move both `ptr1` and `ptr2` one step at a time until they meet (`ptr1 == ptr2`).
  - The node where they meet is the start of the cycle. Return this node.

# Solutions
### Java

```java
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle ( ListNode head ) { ListNode fast = head , slow = head ; while ( fast != null && fast . next != null ) { slow = slow . next ; fast = fast . next . next ; if ( slow == fast ) { ListNode ans = head ; while ( ans != slow ) { ans = ans . next ; slow = slow . next ; } return ans ; } } return null ; } }
```

### JavaScript

```javascript
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {ListNode} */ var detectCycle = function ( head ) { let [ slow , fast ] = [ head , head ]; while ( fast && fast . next ) { slow = slow . next ; fast = fast . next . next ; if ( slow === fast ) { let ans = head ; while ( ans !== slow ) { ans = ans . next ; slow = slow . next ; } return ans ; } } return null ; };
```

### CPP

```cpp
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode * detectCycle ( ListNode * head ) { ListNode * fast = head ; ListNode * slow = head ; while ( fast && fast -> next ) { slow = slow -> next ; fast = fast -> next -> next ; if ( slow == fast ) { ListNode * ans = head ; while ( ans != slow ) { ans = ans -> next ; slow = slow -> next ; } return ans ; } } return nullptr ; } };
```

### Python

```python
# 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 : slow = fast = head has_cycle = False while not has_cycle and fast and fast . next : slow , fast = slow . next , fast . next . next has_cycle = slow == fast if not has_cycle : return None p = head while p != slow : p , slow = p . next , slow . next return p ############# class Solution : def detectCycle ( self , head : Optional [ ListNode ]) -> Optional [ ListNode ]: fast = slow = head while fast and fast . next : slow = slow . next fast = fast . next . next if slow == fast : ans = head while ans != slow : ans = ans . next slow = slow . next return ans
```