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()
        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

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