How to Detect the Starting Node of a Cycle in a Linked List
Tags: leetcode, python, algorithms, datastructures
Published: 2024-06-18 20:09:57

## Introduction

In this blog post, we'll explore a popular problem from LeetCode: **Linked List Cycle II**. This problem is all about detecting the start of a cycle in a linked list. We will go through the problem description, understand two approaches to solve it, and then look at their implementations in Python.

---

## Problem Statement

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

A cycle in a linked list occurs when a node’s `next` pointer points back to a previous node, creating a loop. The problem does not give us the position directly, so we need to determine if a cycle exists and find its starting point.

---

## Approach 1: Using a Set

The first approach to solve this problem is by using a set to keep track of visited nodes. As we traverse the linked list, we add each node to the set. If we encounter a node that is already in the set, then that node is the start of the cycle.

### Implementation

```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:
        visited = set()
        current = head
        
        while current:
            if current in visited:
                return current
            visited.add(current)
            current = current.next
        
        return None
```
### Explanation

#### Approach 1: Using a Set

**Initialization:**
- Create an empty set called `visited`.
- Initialize a variable `current` to the head of the list.

**Cycle Detection:**
- Traverse the list, adding each node to the `visited` set.
- If a node is already in the set, it means we have encountered the start of the cycle.
- Return the node where the cycle begins.
- If the traversal ends (i.e., `current` becomes `None`), return `None` as there is no cycle.

#### Approach 2: Floyd’s Tortoise and Hare Algorithm

The second approach is using Floyd’s Cycle-Finding Algorithm, also known as the Tortoise and Hare algorithm. This method involves two main steps:

**Detection of Cycle:**
- Use two pointers, a slow pointer (`slow`) and a fast pointer (`fast`).
- Move `slow` by one step and `fast` by two steps.
- If there is a cycle, `slow` and `fast` will meet at some point inside the cycle.

**Finding the Start of the Cycle:**
- Once a cycle is detected, reset one pointer to the head of the linked list.
- Move both pointers one step at a time.
- The point at which they meet is the start of the cycle.

### Implementation

```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:
        if not head:
            return None
        
        slow, fast = head, head
        
        while True:
            if not fast or not fast.next:
                return None
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                break
        
        fast = head
        while fast != slow:
            fast = fast.next
            slow = slow.next
        
        return fast
```

### Explanation

**Initialization:**
- Check if the head is `None`. If it is, there’s no cycle, and we return `None`.

**Cycle Detection:**
- Initialize two pointers, `slow` and `fast`, both pointing to the head of the list.
- Traverse the list with `slow` moving one step at a time and `fast` moving two steps.
- If `fast` or `fast.next` becomes `None`, there’s no cycle, and we return `None`.
- If `slow` equals `fast`, a cycle is detected.

**Finding the Start Node:**
- Reset `fast` to the head of the list.
- Move both `slow` and `fast` one step at a time until they meet.
- The node where they meet is the start of the cycle.

### Conclusion

We have discussed two efficient methods to detect the start of a cycle in a linked list: using a set and Floyd’s Tortoise and Hare algorithm. Both methods have their own advantages and are useful in different scenarios.

- **Using a Set:** Simpler to understand and implement but uses O(n) extra space.
- **Floyd’s Algorithm:** More efficient in terms of space complexity (O(1)) but slightly more complex to implement.

I hope this explanation helps you understand how to tackle the Linked List Cycle II problem. Feel free to ask questions or share your thoughts in the comments!