Practice › Linked List
Detect a Cycle in a Linked List
Easy · Linked List · Asked at Amazon, Microsoft, Google, Goldman Sachs, TCS
The list is built from the values, and then the last node is linked back to the node at index pos (0-based). If pos = -1, there is no cycle. Print YES if the list has a cycle, otherwise NO. Solve it with O(1) extra memory.
Input
First line: n pos. Second line: the n node values.
Output
YES or NO.
Constraints
- 1 ≤ n ≤ 10^5
- -1 ≤ pos < n
Floyd's slow and fast pointers: if they ever meet, there is a cycle.
Example 1
Input
4 1 3 2 0 -4
Output
YES
Example 2
Input
1 -1 1
Output
NO
Hints
- Build the list, then link the tail to node pos (if pos ≥ 0).
- Move slow one step and fast two steps. If fast reaches null there is no cycle; if they meet, there is one.
Approach
Floyd's cycle detection. Inside a cycle, the fast pointer gains one node per step on the slow pointer, so it must catch it; without a cycle, fast falls off the end. Only two pointers are used — no visited set.
Complexity: O(n) time · O(1) extra space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
struct Node {
long long val;
Node *next = nullptr;
Node(long long v) : val(v) {}
};
int main() {
int n, pos;
cin >> n >> pos;
vector<Node *> nodes(n);
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
nodes[i] = new Node(x);
if (i) nodes[i - 1]->next = nodes[i];
}
if (pos >= 0) nodes[n - 1]->next = nodes[pos];
Node *slow = nodes[0], *fast = nodes[0];
bool cycle = false;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
cycle = true;
break;
}
}
cout << (cycle ? "YES" : "NO") << "\n";
return 0;
}Python solution
import sys
class Node:
def __init__(self, val):
self.val, self.next = val, None
data = list(map(int, sys.stdin.read().split()))
n, pos = data[0], data[1]
nodes = [Node(v) for v in data[2 : 2 + n]]
for i in range(n - 1):
nodes[i].next = nodes[i + 1]
if pos >= 0:
nodes[-1].next = nodes[pos]
slow = fast = nodes[0]
cycle = False
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow is fast:
cycle = True
break
print("YES" if cycle else "NO")Java solution
import java.util.*;
public class Main {
static class Node {
long val;
Node next;
Node(long v) { val = v; }
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), pos = sc.nextInt();
Node[] nodes = new Node[n];
for (int i = 0; i < n; i++) {
nodes[i] = new Node(sc.nextLong());
if (i > 0) nodes[i - 1].next = nodes[i];
}
if (pos >= 0) nodes[n - 1].next = nodes[pos];
Node slow = nodes[0], fast = nodes[0];
boolean cycle = false;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
cycle = true;
break;
}
}
System.out.println(cycle ? "YES" : "NO");
}
}Solve Detect a Cycle in a Linked List online · All practice problems