Leetcode 141: Linked List Cycle (with Visualization)

Problem link: https://leetcode.com/problems/linked-list-cycle/

In this article, we will explore the problem of detecting cycles in linked lists and dive into the implementation of Floyd’s cycle-finding algorithm. Along the way, we will use visualizations to illustrate the step-by-step execution of the algorithm. By the end of the article, you will have a clear understanding of how the algorithm works and be able to apply it to solve similar problems.

Problem Description

The problem asks us to determine if a given linked list contains a cycle. A linked list contains a cycle if there is a node in the list that can be reached again by continuously following the next pointer. The goal is to return True if there is a cycle and False otherwise.

Example 1:

Visual representation of example 1

Input: head = [1,2]
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 2:

Visual representation of example 2

Input: head = [1]
Output: false
Explanation: There is no cycle in the linked list.

Approach and Explanation

To solve this problem, we can use Floyd’s cycle-finding algorithm, also known as the “tortoise and hare” algorithm. This algorithm uses two pointers: slow and fast.

1. We start by initializing both slow and fast pointers to the head of the linked list.

2. We iterate through the linked list using the following conditions:

• Move the slow pointer one step at a time by assigning slow = slow.next.
• Move the fast pointer two steps at a time by assigning fast = fast.next.next.
• If there is a cycle in the linked list, the fast the pointer will eventually catch up to the slow pointer.
• If there is no cycle, the fast the pointer will reach the end of the linked list, and we can stop the iteration.

5. During the iteration, if slow and fast become equal at any point, it means there is a cycle in the linked list. We can return True.

6. If the iteration completes without finding a cycle, we can conclude that there is no cycle in the linked list, and we can return False.

Implementation

Here’s the implementation of the solution in Python:

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        # Initialize the slow and fast pointers to the head
        slow, fast = head, head
        
        while fast is not None and fast.next is not None:
            # Move the slow pointer one step at a time
            slow = slow.next
            # Move the fast pointer two steps at a time
            fast = fast.next.next
            
            # If slow and fast meet, there is a cycle
            if slow == fast:
                return True
        
        # No cycle found
        return False

Simulation

Let’s simulate the solution with a sample linked list to demonstrate how the algorithm works.
Suppose we have the following linked list with a cycle:

Linked list with cycle

In this case, the head points to the first node 1, and the next pointer of the last node 6 points back to the node 3, creating a cycle.

Initial state

Initially, both slow and fast are set to the head of the linked list (1).

Visualization of Iteration 1

Iteration 1:

• slow moves to the next node (2)
• fast moves two steps ahead to the next node after 2 (3)

Visualization of Iteration 2

Iteration 2:

• slow moves to the next node (3)
• fast moves two steps ahead to the next node after 4(5)

Visualization of Iteration 2

Iteration 3:

• slow moves to the next node (4)
• fast moves two steps ahead to the next node after 6(3)

Iteration 4:

• slow moves to the next node (5)
• fast moves two steps ahead to the next node after 4(5)

At this point, both slow fast become equal (5 == 5), indicating the presence of a cycle in the linked list.
We return True to indicate that the linked list has a cycle.

This simulation demonstrates how slow and fast pointers move through the linked list and eventually meet when a cycle exists. If there was no cycle, the fast pointer would reach the end of the linked list, and the iteration would terminate without finding a cycle.

Complexity Analysis

The time complexity of this solution is O(n), where n is the number of nodes in the linked list. This is because, in the worst case, we need to iterate through all the nodes in the linked list before concluding whether a cycle exists or not.

The space complexity is O(1) since we are using only two pointers (slow and fast) to track the cycle, and we are not using any additional data structures.