Detect a Cycle

Detecting a cycle in a linked list is a classic problem that comes up when you need to guard against infinite loops—whether you’re processing user sessions, network packets, or graph structures. It tests your ability to reason about pointers and traversal efficiency.

Problem Statement

Given the head of a singly linked list, determine whether the list contains a cycle. A cycle exists if, by following next pointers, you can revisit a node you’ve seen before. Return true if there is a cycle, or false otherwise.

// Definition for singly-linked list node:
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; next = null; }
}

// Function signature:
public boolean hasCycle(ListNode head);

1. Clarify Requirements Before Jumping Into Code

I’ll ask a few quick clarifications:

• Can the input be null or a single-node list? (Yes.)

• Should I detect self-cycles (node.next == node)? (Yes.)

• Is extra memory allowed, or should I aim for O(1) space? (Extra space is allowed but O(1) preferred.)

• Do I need to return the node where the cycle begins, or just a boolean? (Just boolean.)

2. Identify the Category of the Question

This is a linked list cycle detection problem, which fits into common pointer and traversal patterns:

• Fast/slow pointer (Floyd’s algorithm)

• Hash set of visited nodes

• In-place marking by altering pointers or node values

• Recursive detection (less common here)

Recognizing that revisiting a node implies a cycle points to either remembering visited nodes or using two pointers at different speeds.

3. Consider a Brute-Force Approach to Understand the Problem

The simplest idea is to walk the list and store every visited node in a hash set. On each step, check if the current node is already in the set—if it is, return true; if I reach null, return false.

• Time Complexity: O(n) on average

• Space Complexity: O(n) for the set

• Drawback: Uses extra memory equal to list length

4. Brainstorm More Solutions

I’d like to avoid O(n) extra space. What else could catch a cycle? If two pointers move at different speeds—one stepping one node at a time (slow), the other two nodes at a time (fast)—then in a cyclic list the fast pointer will eventually “lap” the slow pointer. In a non-cyclic list, fast reaches null first.

To rediscover this in real time, I imagine walking (slow) while my friend jogs twice as fast (fast). If there’s a looped track, my friend will catch up; if the track ends, they’ll run out of road. I don’t need extra memory—just two references—and I only traverse the list once.

5. Discuss Trade-Offs Between Your Solutions

Approach	Time	Space	Pros	Cons
Hash Set	O(n)	O(n)	Easy to implement	Extra O(n) memory
Fast/Slow Pointer	O(n)	O(1)	No extra memory, elegant	Must reason carefully about loops
In-Place Marking	O(n)	O(1)	Also constant space	Destroys list structure

Fast/slow pointer (Floyd’s) offers O(1) space without mutating nodes.

6. Write Pseudocode to Structure Your Thoughts

function hasCycle(head):
    slow = head
    fast = head

    while fast ≠ null and fast.next ≠ null:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return true

    return false

7. Consider Edge Cases

• Empty list (head = null) → returns false

• Single node, no cycle → head.next = null → false

• Single node, self-cycle (head.next = head) → true

• Two nodes linking back → cycle detected

• Long list with cycle starting late → pointers still meet

8. Write Full Code Syntax

public class Solution {
    public boolean hasCycle(ListNode head) {
        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;
    }
}

9. Test Your Code

public static void main(String[] args) {
    Solution sol = new Solution();

    // Helper to build lists and form cycles omitted for brevity

    // Test 1: empty
    assert sol.hasCycle(null) == false;

    // Test 2: single node, no cycle
    ListNode a = new ListNode(1);
    assert sol.hasCycle(a) == false;

    // Test 3: single node, self-cycle
    a.next = a;
    assert sol.hasCycle(a) == true;

    // Test 4: two nodes, no cycle
    ListNode b = new ListNode(2);
    a.next = b;
    b.next = null;
    assert sol.hasCycle(a) == false;

    // Test 5: two nodes, cycle
    b.next = a;
    assert sol.hasCycle(a) == true;

    // Test 6: longer list with late cycle
    ListNode head = new ListNode(0), curr = head;
    for (int i = 1; i <= 9; i++) {
        curr.next = new ListNode(i);
        curr = curr.next;
    }
    // link tail back to node 4
    ListNode cycleStart = head;
    for (int i = 0; i < 4; i++) cycleStart = cycleStart.next;
    curr.next = cycleStart;
    assert sol.hasCycle(head) == true;

    System.out.println("All tests passed!");
}

10. Key Lessons to Remember for Future Questions

• Fast/slow pointer, also known as Floyd's algorithm, is the go-to pattern for cycle detection in O(1) space.

• Brute-force with a hash set clarifies correctness before optimizing space.

• Always check both fast != null and fast.next != null to avoid null-pointer exceptions.

• Visual analogies (walker and runner on a track) help rediscover algorithms under pressure.

• Edge-case tests (empty, single-node, tail cycles) confirm reliability.

• Communicating trade-offs—memory vs. simplicity—demonstrates thought process.

Good Luck and Happy Coding!