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

This content originally appeared on DEV Community and was authored by Saif Matab

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!

This content originally appeared on DEV Community and was authored by Saif Matab

Print Share Comment Cite Upload Translate Updates

APA

Saif Matab | Sciencx (2024-06-18T20:09:57+00:00) How to Detect the Starting Node of a Cycle in a Linked List. Retrieved from https://www.scien.cx/2024/06/18/how-to-detect-the-starting-node-of-a-cycle-in-a-linked-list-2/

MLA

" » How to Detect the Starting Node of a Cycle in a Linked List." Saif Matab | Sciencx - Tuesday June 18, 2024, https://www.scien.cx/2024/06/18/how-to-detect-the-starting-node-of-a-cycle-in-a-linked-list-2/

HARVARD

Saif Matab | Sciencx Tuesday June 18, 2024 » How to Detect the Starting Node of a Cycle in a Linked List., viewed ,<https://www.scien.cx/2024/06/18/how-to-detect-the-starting-node-of-a-cycle-in-a-linked-list-2/>

VANCOUVER

Saif Matab | Sciencx - » How to Detect the Starting Node of a Cycle in a Linked List. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2024/06/18/how-to-detect-the-starting-node-of-a-cycle-in-a-linked-list-2/

CHICAGO

" » How to Detect the Starting Node of a Cycle in a Linked List." Saif Matab | Sciencx - Accessed . https://www.scien.cx/2024/06/18/how-to-detect-the-starting-node-of-a-cycle-in-a-linked-list-2/

IEEE

" » How to Detect the Starting Node of a Cycle in a Linked List." Saif Matab | Sciencx [Online]. Available: https://www.scien.cx/2024/06/18/how-to-detect-the-starting-node-of-a-cycle-in-a-linked-list-2/. [Accessed: ]

rf:citation

» How to Detect the Starting Node of a Cycle in a Linked List | Saif Matab | Sciencx | https://www.scien.cx/2024/06/18/how-to-detect-the-starting-node-of-a-cycle-in-a-linked-list-2/ |

Please log in to upload a file.

There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.