Detect a Loop in a Linked List
Solve this Problemhead of a singly linked list, return true if the list contains a cycle — some node's next pointer leads back to an earlier node instead of eventually reaching null.
Since a cyclic list can never be fully printed or walked to completion, this test's inputs are described as (values, pos): build a normal list from the values, then point the last node's next at the node located at index pos (0-indexed). pos = -1 means no cycle at all. The optimal solution — Floyd's Cycle DetectionFloyd's Cycle DetectionAlso called the "tortoise and hare" algorithm. Two pointers move through the list at different speeds (1 step and 2 steps). If a cycle exists, both get trapped inside it and are guaranteed to eventually land on the same node — since the faster one gains exactly one node on the slower one every step. — detects this in O(1) extra space, without ever storing a single visited node.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes in head ≤ 10⁴ - ◆
-10⁹ ≤ node value ≤ 10⁹ - ◆
A cyclic test list is described as (vals, pos) — the last node's next points back to index pos (0-indexed); pos = -1 means no cycle
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
| 1 | class Solution { |
| 2 | public boolean hasLoop(Node head) { |
| 3 | Node slow = head, fast = head; |
| 4 | while (fast != null && fast.next != null) { |
| 5 | slow = slow.next; |
| 6 | fast = fast.next.next; |
| 7 | if (slow == fast) { |
| 8 | return true; |
| 9 | } |
| 10 | } |
| 11 | return false; |
| 12 | } |
| 13 | } |
| 14 |
3 (node 0)3 (node 0)Both slow and fast start at head.
Approach & Solutions
Brute Force — Hash Set of Visited Nodes
GoodWalk the list, adding each node to a hash set as it's visited. If a node is ever seen that's already in the set, the list has looped back on itself — a cycle. If the walk instead reaches null, every node was distinct and there's no cycle. Correct, but storing every visited node costs O(n) extra space.
O(n)O(n)1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public boolean hasLoop(Node head) {
9 Set<Node> visited = new HashSet<>();
10 Node curr = head;
11 while (curr != null) {
12 if (visited.contains(curr)) {
13 return true;
14 }
15 visited.add(curr);
16 curr = curr.next;
17 }
18 return false;
19 }
20}Optimal — Floyd's Cycle Detection (Tortoise and Hare)
OptimalMove slow one step and fast two steps at a time. If there's no cycle, fast reaches null first, same as any normal traversal. If there is a cycle, both pointers eventually get trapped inside it — and because fast gains on slow by exactly one node every step, that gap must eventually shrink to zero, meaning they land on the same node.
O(n)O(1)1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public boolean hasLoop(Node head) {
9 Node slow = head, fast = head;
10 while (fast != null && fast.next != null) {
11 slow = slow.next;
12 fast = fast.next.next;
13 if (slow == fast) {
14 return true;
15 }
16 }
17 return false;
18 }
19}