Find the First Node of a Loop in a Linked List
Solve this Problemhead of a singly linked list that may contain a cycle, return the 0-indexed position of the node where the cycle begins, or -1 if there is no cycle.
Since node values may repeat, the answer has to be a position, not a value — otherwise an earlier duplicate could be mistaken for the loop's actual start. The optimal solution runs Floyd's Cycle DetectionFloyd's Cycle DetectionThe "tortoise and hare" algorithm: slow and fast pointers moving at 1 and 2 steps per iteration. Once they meet inside a cycle, resetting one pointer to head and advancing both at equal speed makes them meet again exactly at the cycle's first node — a property that follows from the arithmetic of how far each pointer traveled to reach the meeting point. in two phases: first find where slow and fast meet, then reset one pointer to head and walk both one step at a time until they meet again — that second meeting point is the loop's start.
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 - ◆
The answer is the 0-indexed position of the loop's first node, or -1 if there is no loop — a position, not a value, since values may repeat
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
| 1 | class Solution { |
| 2 | public int findLoopStartIndex(Node head) { |
| 3 | Node slow = head, fast = head; |
| 4 | boolean hasLoop = false; |
| 5 | while (fast != null && fast.next != null) { |
| 6 | slow = slow.next; |
| 7 | fast = fast.next.next; |
| 8 | if (slow == fast) { |
| 9 | hasLoop = true; |
| 10 | break; |
| 11 | } |
| 12 | } |
| 13 | if (!hasLoop) { |
| 14 | return -1; |
| 15 | } |
| 16 | slow = head; |
| 17 | int index = 0; |
| 18 | while (slow != fast) { |
| 19 | slow = slow.next; |
| 20 | fast = fast.next; |
| 21 | index++; |
| 22 | } |
| 23 | return index; |
| 24 | } |
| 25 | } |
| 26 |
3 (node 0)3 (node 0)falsePhase 1: both slow and fast start at head, hunting for a meeting point.
Approach & Solutions
Brute Force — Hash Set, Track Index While Traversing
GoodWalk the list, recording the index each node is first seen at in a hash map. If a node is ever encountered that's already in the map, the index it was first recorded at is exactly where the loop starts — because that's the node the tail eventually loops back to. 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 int findLoopStartIndex(Node head) {
9 Map<Node, Integer> visited = new HashMap<>();
10 Node curr = head;
11 int index = 0;
12 while (curr != null) {
13 if (visited.containsKey(curr)) {
14 return visited.get(curr);
15 }
16 visited.put(curr, index);
17 curr = curr.next;
18 index++;
19 }
20 return -1;
21 }
22}Optimal — Floyd's Algorithm, Reset One Pointer to Head
OptimalPhase 1: run the usual slow/fast pointers until they meet somewhere inside the cycle (or fast reaches the end, meaning no loop). Phase 2: reset slow to head, leave fast at the meeting point, then move both one step at a time. A property of how the meeting point falls out of phase 1 guarantees these two now-equal-speed pointers meet again exactly at the loop's first 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 int findLoopStartIndex(Node head) {
9 Node slow = head, fast = head;
10 boolean hasLoop = false;
11 while (fast != null && fast.next != null) {
12 slow = slow.next;
13 fast = fast.next.next;
14 if (slow == fast) {
15 hasLoop = true;
16 break;
17 }
18 }
19 if (!hasLoop) {
20 return -1;
21 }
22 slow = head;
23 int index = 0;
24 while (slow != fast) {
25 slow = slow.next;
26 fast = fast.next;
27 index++;
28 }
29 return index;
30 }
31}