Saif Matab

Posted on

# How to Detect the Starting Node of a Cycle in a Linked List

## 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

``````# 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 current:
if current in visited:
return 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

``````# 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:
return None

while True:
if not fast or not fast.next:
return None
slow = slow.next
fast = fast.next.next
if slow == fast:
break

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!