Detect a Cycle in a Linked List

In this article, we will solve the problem of detecting a cycle in a linked list. This is a common problem that can occur in real-world applications, such as network routing, where detecting cycles is essential.

Problem Statement: Given the head of a linked list, determine whether the linked list contains a cycle. A cycle occurs when a node’s next pointer points back to a previous node in the list, creating a loop.

Example:

Input: 1 -> 2 -> 3 -> 4 -> 2 (cycle back to 2) 

Output: True 

Explanation: There is a cycle in the linked list as node 4 points back to node 2.

Solution:

To detect a cycle in a linked list, we can use Floyd’s Cycle-Finding Algorithm, also known as the Tortoise and Hare Algorithm. This algorithm uses two pointers that move at different speeds to determine if a cycle exists.

Steps to Solve:

1.    Initialize Pointers:

o   Use two pointers, slow and fast. Initially, both pointers are present at the head of the linked list.

2.    Move Pointers:

o   Move the slow pointer one step at a time and the fast pointer two steps at a time.

3.    Detect Cycle:

o   If there is no cycle, the fast pointer will reach the end of the list (null) before the slow pointer.

o   If there is a cycle, the fast pointer will eventually meet the slow pointer within the cycle.

4.    Return Result:

o   If the fast pointer meets the slow pointer, return true indicating a cycle.

o   If the fast pointer reaches the end of the list, return false indicating no cycle.

Time Complexity: O(N)

Space Complexity: O(1)