Linked List Cycle | Leetcode 141 | Floyd’s Cycle Detection

Given head, the head of a linked list, determine if the linked list has a cycle in it. There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Return true if there is a cycle in the linked list, otherwise return false.

Here’s the [Problem Link] to begin with.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

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

Example 3:

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

Constraints:

• The number of the nodes in the list is in the range [0, 104].
• -105 <= Node.val <= 105
• pos is -1 or a valid index in the linked-list.

Follow up: Can you solve it using O(1) (i.e. constant) memory?

Solution 1: Brute Force Approach (Using Set)

Intuition

Imagine you’re walking through a maze and want to know if you’re going in circles. One simple way is to drop a breadcrumb at every place you visit. If you ever find a breadcrumb you’ve already dropped, you know you’re walking in a circle! We use the same idea here – store every node we visit, and if we see the same node again, there’s a cycle.

Detailed Approach

1. Create a Tracking System: Use a set to remember all the nodes we’ve visited
2. Walk Through the List: Move through each node one by one
3. Check Before Adding: At each node, check if we’ve seen it before
4. Found a Cycle: If we find a node we’ve already visited, return true
5. Reached the End: If we reach the end (None), there’s no cycle

Code

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        temp = head              # Current node we're examining
        node_set = set()         # Set to store visited nodes
        
        while temp is not None:
            if temp in node_set: # Check if we've seen this node before
                return True      # Found a cycle!
            node_set.add(temp)   # Remember this node for future
            temp = temp.next     # Move to the next node
        
        return False            # Reached end, no cycle found

Code Explanation

We start from the head and visit each node one by one. Before moving to the next node, we check if the current node is already in our set. If it is, we’ve found a cycle because we’re visiting the same node twice. If it’s not in the set, we add it and continue. If we reach the end of the list (temp becomes None), it means there’s no cycle.

Dry Run

Let’s trace through a list with cycle: 1 -> 2 -> 3 -> 2 (3 points back to 2)

Step 1: temp=1, node_set={}, add 1: node_set={1}
Step 2: temp=2, node_set={1}, add 2: node_set={1, 2}
Step 3: temp=3, node_set={1, 2}, add 3: node_set={1, 2, 3}
Step 4: temp=2, node_set={1, 2, 3}, 2 is already in set → return True

Result: Cycle detected!

Time and Space Complexity

• Time Complexity: O(n) – We visit each node at most once before detecting the cycle
• Space Complexity: O(n) – In worst case, we store all nodes in the set

Simplifying It

This approach is straightforward – keep a record of everywhere you’ve been, and if you end up somewhere you’ve already been, you know you’re going in circles. However, it uses extra memory to store all the visited nodes.

Solution 2: Optimal Approach (Floyd’s Cycle Detection – Two Pointers)

Intuition

Imagine two people running on a circular track – one person runs at normal speed, and another runs twice as fast. If the track is circular, the faster runner will eventually lap the slower runner and they’ll meet. If the track has an end, the fast runner will just reach the finish line first. This is exactly how we detect cycles!

Detailed Approach

1. Set Up Two Runners: Create two pointers – slow (moves 1 step) and fast (moves 2 steps)
2. Start the Race: Both start from the head of the linked list
3. Move at Different Speeds: Slow moves 1 node at a time, fast moves 2 nodes at a time
4. Check for Meeting: If there’s a cycle, fast will eventually catch up to slow
5. Check for End: If fast reaches the end (None), there’s no cycle

Code

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = head          # Slow pointer (tortoise) - moves 1 step
        fast = head          # Fast pointer (hare) - moves 2 steps

        while fast is not None and fast.next is not None:
            slow = slow.next      # Move slow pointer 1 step
            fast = fast.next.next # Move fast pointer 2 steps
            
            if slow == fast:      # Pointers met - cycle detected!
                return True

        return False             # Fast reached end - no cycle

Code Explanation

We use two pointers moving at different speeds. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. If there’s no cycle, the fast pointer will reach the end first. But if there’s a cycle, both pointers will keep moving in the cycle forever, and eventually the fast pointer will catch up to the slow pointer from behind. When they meet, we know there’s a cycle.

Dry Run

Let’s trace through a list with cycle: 1 -> 2 -> 3 -> 2 (3 points back to 2)

Initial: slow=1, fast=1

Step 1:

• slow moves to 2
• fast moves to 3
• slow ≠ fast

Step 2:

• slow moves to 3
• fast moves to 2 (following the cycle)
• slow ≠ fast

Step 3:

• slow moves to 2 (following the cycle)
• fast moves to 3
• slow ≠ fast

Step 4:

• slow moves to 3
• fast moves to 2
• slow ≠ fast

Step 5:

• slow moves to 2
• fast moves to 3
• slow ≠ fast

Wait, let me recalculate this more carefully…

Initial: slow=1, fast=1

Step 1: slow=2, fast=3, slow ≠ fast
Step 2: slow=3, fast=2 (cycle), slow ≠ fast
Step 3: slow=2 (cycle), fast=3, slow ≠ fast
Step 4: slow=3, fast=2, slow ≠ fast
Step 5: slow=2, fast=3, slow ≠ fast

Actually, they will meet eventually as the fast pointer will catch up in the cycle.

Result: Eventually slow == fast, return True

Time and Space Complexity

• Time Complexity: O(n) – In the worst case, we might need to traverse the entire list
• Space Complexity: O(1) – We only use two pointer variables, no extra space

Simplifying It

This is like the classic “tortoise and hare” race. The key insight is that if there’s a cycle, the faster moving pointer will eventually lap the slower one. If there’s no cycle, the fast pointer will simply reach the end first. This approach is memory-efficient because we don’t need to store any visited nodes.

Summary

The two pointers approach is generally preferred because it uses constant space while maintaining the same time efficiency. However, the brute force approach is more intuitive and easier to understand when you’re first learning about cycle detection.

Both solutions are valid, but Floyd’s Cycle Detection algorithm (two pointers) is considered the optimal solution for this problem due to its space efficiency!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.