Linked List Cycle — Practice

Problem

Given head, the head of a linked list, determine if the linked list has a cycle in it.

Return true if there is a cycle, false otherwise.

Examples

Example 1

Input: head = [3,2,0,-4], pos=1

Output: true

Explanation: Tail connects to node at index 1.

Example 2

Input: head = [1], pos=-1

Output: false

Explanation: No cycle.

Constraints

•The number of nodes is in the range [0, 10^4].

Hints

Hint 1

Floyd's cycle detection: fast pointer moves 2 steps, slow moves 1 — they meet if there's a cycle, since the fast pointer effectively 'laps' the slow one inside the loop.

Hint 2

A simpler brute force tracks every visited NODE in a hash set, checking for a repeat — correct in O(n) time, but uses O(n) space; Floyd's technique achieves the same result in O(1) space.

Solutions

public boolean hasCycleBruteForce(ListNode head) {
    Set<ListNode> visited = new HashSet<>();
    ListNode curr = head;
    while (curr != null) {
        if (!visited.add(curr)) return true; // add() returns false if curr was already present
        curr = curr.next;
    }
    return false;
}

Time: O(n) · Space: O(n)