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.
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.
The number of nodes is in the range [0, 10^4].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.
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.
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)