# Linked List Cycle
**Difficulty:** EASY
[External](https://leetcode.com/problems/linked-list-cycle)
Canonical: https://scaleengineer.com/dsa/problems/linked-list-cycle
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Hash Table, Linked List
**Companies:** [Cisco](https://scaleengineer.com/companies/cisco), [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Intel](https://scaleengineer.com/companies/intel), [Oracle](https://scaleengineer.com/companies/oracle), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [SAP](https://scaleengineer.com/companies/sap), [Samsung](https://scaleengineer.com/companies/samsung), [Uber](https://scaleengineer.com/companies/uber), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Wipro](https://scaleengineer.com/companies/wipro), [Yahoo](https://scaleengineer.com/companies/yahoo), [ZScaler](https://scaleengineer.com/companies/zscaler), [Autodesk](https://scaleengineer.com/companies/autodesk), [DE Shaw](https://scaleengineer.com/companies/de-shaw)
---
## Problem
Given `head`, the head of a linked list, determine if the linked list has a cycle in it.

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

Return `true` _if there is a cycle in the linked list_. Otherwise, return `false`.

**Example 1:**

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

**Input:** head = [3,2,0,-4], pos = 1
**Output:** true
**Explanation:** There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

**Example 2:**

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

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

**Example 3:**

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

**Input:** head = [1], pos = -1
**Output:** false
**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
## Using a Hash Set
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, it means we have found a cycle.
**Time:** O(N) · **Space:** O(N)
**Pros:** Simple to understand and implement.
**Cons:** Requires extra space proportional to the number of nodes, which can be significant for large lists.; Does not meet the follow-up requirement of O(1) space.
### Explanation
The core idea is to keep a record of every node we have visited. A `HashSet` is an ideal data structure for this because it provides average O(1) time complexity for insertion and lookup operations. We traverse the list from the head, and for each node, we check if we have seen it before by looking it up in our hash set. If we find the node in the set, it confirms that we are visiting it for the second time, which is only possible if there's a cycle. If the node is not in the set, we add it and move to the next node. If we successfully traverse the entire list and reach the `null` end, it means no node was visited twice, and therefore, no cycle exists.

```java
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
import java.util.HashSet;
import java.util.Set;

public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> visitedNodes = new HashSet<>();
        ListNode current = head;
        while (current != null) {
            if (visitedNodes.contains(current)) {
                return true; // Cycle detected
            }
            visitedNodes.add(current);
            current = current.next;
        }
        return false; // No cycle found
    }
}
```
### Algorithm
1. Initialize an empty `HashSet` to store references to visited nodes.
2. Create a pointer `current` and initialize it with the `head` of the linked list.
3. Traverse the list by iterating while `current` is not `null`.
4. In each iteration, check if the `current` node is already present in the `HashSet`.
5. If it is, a cycle has been detected, and we can return `true`.
6. If it's not, add the `current` node to the `HashSet` and advance the pointer to the next node (`current = current.next`).
7. If the loop completes without finding a duplicate node, it means we've reached the end of the list (`null`), so no cycle exists. Return `false`.

## Floyd's Tortoise and Hare Algorithm (Two Pointers)
This is an optimal approach that uses two pointers, a 'slow' pointer and a 'fast' pointer, to detect a cycle in constant space. The slow pointer moves one step at a time, while the fast pointer moves two steps.
**Time:** O(N) · **Space:** O(1)
**Pros:** Optimal space complexity of O(1), satisfying the follow-up question.; Efficient time complexity of O(N).; Does not modify the input linked list.
**Cons:** The logic can be slightly less intuitive to understand initially compared to the hash set method.
### Explanation
This classic algorithm is also known as the 'tortoise and the hare' algorithm. The intuition behind it can be visualized as two runners on a track. If the track is a straight line, the faster runner will simply reach the end first. However, if the track is circular, the faster runner will eventually lap the slower runner.

We apply this to our linked list. The `slow` pointer moves one node at a time, and the `fast` pointer moves two nodes at a time. 
- If the list has no cycle, the `fast` pointer will reach the end (`null`) before the `slow` pointer, and we can conclude there is no cycle.
- If the list does have a cycle, the `fast` pointer will enter the cycle first, followed by the `slow` pointer. Once both are in the cycle, the `fast` pointer gains on the `slow` pointer by one node in each iteration. Since they are moving at different speeds in a finite-length cycle, they are guaranteed to meet at some point. The detection of this meeting (`slow == fast`) confirms the presence of a cycle.

```java
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            
            if (slow == fast) {
                return true; // Cycle detected
            }
        }
        
        return false; // No cycle found
    }
}
```
### Algorithm
1. Initialize two pointers, `slow` and `fast`, both pointing to the `head` of the list.
2. Check for the edge case where the list is empty (`head == null`). If so, return `false`.
3. Enter a loop that continues as long as the `fast` pointer and its `next` node are not `null`. This prevents `NullPointerException` when advancing the fast pointer.
4. Inside the loop, advance the `slow` pointer by one step (`slow = slow.next`).
5. Advance the `fast` pointer by two steps (`fast = fast.next.next`).
6. After moving the pointers, check if `slow` and `fast` are pointing to the same node (`slow == fast`).
7. If they are the same, a cycle is detected. Return `true`.
8. If the loop terminates (because `fast` or `fast.next` is `null`), it means the end of the list was reached without the pointers meeting. Return `false`.

# Solutions
### CSharp

```csharp
/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public bool HasCycle ( ListNode head ) { var fast = head ; var slow = head ; while ( fast != null && fast . next != null ) { fast = fast . next . next ; slow = slow . next ; if ( fast == slow ) { return true ; } } return false ; } }
```

### Java

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

### JavaScript

```javascript
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {boolean} */ var hasCycle =
  function (head) {
    let slow = head;
    let fast = head;
    while (fast && fast.next) {
      slow = slow.next;
      fast = fast.next.next;
      if (slow === fast) {
        return true;
      }
    }
    return false;
  };

```

### CPP

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

### Python

```python
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution : def hasCycle ( self , head : ListNode ) -> bool : slow = fast = head while fast and fast . next : slow , fast = slow . next , fast . next . next if slow == fast : return True return False
```