Practice › Linked List
Starting Point of a Loop
Medium · Linked List · Asked at Amazon, Microsoft, Google, Qualcomm
The list is built like in "Detect a Cycle": the last node links back to index pos (or nowhere if pos = -1). Print the index of the node where the cycle begins, or -1 if there is no cycle. Values can repeat, so find the node itself — not a value.
Input
First line: n pos. Second line: the n node values.
Output
The 0-based index of the first node of the cycle, or -1.
Constraints
- 1 ≤ n ≤ 10^5
- -1 ≤ pos < n
After slow and fast meet, move one pointer back to the head; advancing both one step at a time, they meet at the start of the cycle.
Example 1
Input
4 1 3 2 0 -4
Output
1
Example 2
Input
2 -1 1 2
Output
-1
Hints
- First detect the cycle with slow/fast pointers.
- Then put one pointer back at the head and move both one step at a time — they meet exactly at the first node of the cycle.
Approach
Let the head-to-cycle distance be a and the cycle length c. When slow and fast meet, slow has walked a + b and fast 2(a + b), so a + b is a multiple of c — meaning a more steps from the meeting point lands on the cycle start. Resetting one pointer to the head and stepping both by one makes them meet there. To print the index, keep a map from node to index (or walk from the head counting).
Complexity: O(n) time · O(1) extra space for the algorithm
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
struct Node {
long long val;
Node *next = nullptr;
int idx;
Node(long long v, int i) : val(v), idx(i) {}
};
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, i);
if (i) nodes[i - 1]->next = nodes[i];
}
if (pos >= 0) nodes[n - 1]->next = nodes[pos];
Node *slow = nodes[0], *fast = nodes[0];
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
slow = nodes[0];
while (slow != fast) slow = slow->next, fast = fast->next;
cout << slow->idx << "\n";
return 0;
}
}
cout << -1 << "\n";
return 0;
}Python solution
import sys
class Node:
def __init__(self, val, idx):
self.val, self.idx, self.next = val, idx, None
data = list(map(int, sys.stdin.read().split()))
n, pos = data[0], data[1]
nodes = [Node(v, i) for i, v in enumerate(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]
ans = -1
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow is fast:
slow = nodes[0]
while slow is not fast:
slow, fast = slow.next, fast.next
ans = slow.idx
break
print(ans)Java solution
import java.util.*;
public class Main {
static class Node {
long val;
int idx;
Node next;
Node(long v, int i) { val = v; idx = i; }
}
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(), i);
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];
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
slow = nodes[0];
while (slow != fast) { slow = slow.next; fast = fast.next; }
System.out.println(slow.idx);
return;
}
}
System.out.println(-1);
}
}Solve Starting Point of a Loop online · All practice problems