1. Understanding the Problem

You are given the head of a linked list. Your task is to determine if the linked list has a cycle in it. If there is a cycle, return True. If there is no cycle, return False.

What is a Cycle?

A cycle occurs if there is some node in the list that can be reached again by continuously following the next pointer. Instead of the list eventually pointing to null (the end of the line), the tail node points back to a previous node, creating an infinite loop.

The Core Constraint (The Trap):

If a list has a cycle, standard iteration (while node != null) will trap you in an infinite loop, crashing your program or triggering a "Time Limit Exceeded" error.

2. The Naive Approach: The Hash Set

The most intuitive way to solve this is to keep a record of every node you have visited. As you traverse the linked list, you add each node to a Hash Set.

Before adding a node, you ask: "Is this node already in my set?" If the answer is yes, you have just proved that a cycle exists. If you reach null, you know there is no cycle.

Trade-off Analysis

While this logic is sound and perfectly valid, it comes at a memory cost:

• Time Complexity: O(N) — You traverse the list once. Hash Set lookups take O(1) time.
• Space Complexity: O(N) — In the worst-case scenario (no cycle), you have to store every single node in the list inside your Hash Set. In enterprise systems with massive data pipelines, this extra memory overhead is frowned upon.

3. The Optimal Approach: Fast and Slow Pointers (O(1) Space)

To pass a senior-level technical interview, we want to achieve an O(1) space complexity. We can do this without tracking our history by using two pointers moving at different speeds: the Tortoise (slow) and the Hare (fast).

Imagine two runners on a track. One runs at 1 mph, the other at 2 mph. If the track is a straight line, the fast runner will reach the finish line and the race ends. But if the track is a circle (a cycle), the fast runner will eventually lap the slow runner from behind. They are mathematically guaranteed to meet at the exact same spot at some point.

We apply this exact logic to our pointers. If they ever point to the same node, a cycle exists. If the fast pointer reaches null, the track is straight (no cycle).

4. The Logic Step-by-Step

1. The Empty List Check: If the head is null, or there is only one node pointing to null, return False immediately.
2. Initialize a slow pointer at the head of the list.
3. Initialize a fast pointer also at the head of the list.
4. Traverse the List: Create a loop that continues as long as fast is not null AND fast.next is not null (we must check fast.next because the fast pointer takes two steps at a time).
   • Move the slow pointer forward by 1 step (slow = slow.next).
   • Move the fast pointer forward by 2 steps (fast = fast.next.next).
   • The Collision Check: If slow == fast, the fast pointer has lapped the slow pointer. Return True!
5. If the loop naturally finishes and breaks, it means the fast pointer hit the end of the list. Return False.

5. Complexity Analysis

• Time Complexity: O(N) — If there is no cycle, the fast pointer reaches the end in N/2 steps. If there is a cycle, the distance between the two pointers decreases by 1 on each iteration, meaning they will meet in at most N steps. Overall time is linear.
• Space Complexity: O(1) — We only use two pointers, regardless of how large the linked list is. We have successfully eliminated the need for extra memory!

6. Code Implementations

Expand the sections below to see the optimal O(1) space "Tortoise and Hare" implementations across different languages.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head) -> bool:
        # If the list is empty or has only one node, no cycle is possible
        if not head or not head.next:
            return False
            
        slow = head
        fast = head
        
        # Fast pointer moves 2 steps, so we must check fast and fast.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            
            # If they meet, a cycle exists
            if slow == fast:
                return True
                
        # Fast reached the end of the list, no cycle
        return False

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            
            if (slow == fast) {
                return true;
            }
        }
        
        return false;
    }
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == nullptr || head->next == nullptr) {
            return false;
        }
        
        ListNode *slow = head;
        ListNode *fast = head;
        
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            
            if (slow == fast) {
                return true;
            }
        }
        
        return false;
    }
};

7. Conclusion: You Are Ready

Congratulations, you have just mastered Floyd's Cycle-Finding Algorithm. The "Fast and Slow Pointers" pattern is a foundational tool that you will reuse in multiple advanced scenarios, such as finding the exact node where a cycle begins, or locating the exact middle of a linked list. By visualizing the "runners on a track," you transformed an inefficient memory-heavy approach into an elegant O(1) space solution. Keep this mental model sharp, and you will confidently navigate any pointer-based interview question!