Log inSign up
mediumLeetCodeNot Started

Linked List Cycle II

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Linked List
Solve on LeetCode
Lesson

Problem Statement

Given the head of a linked list, return *the node where the cycle begins*. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that `pos` is not passed as a parameter.

Do not modify the linked list.

Example 1 · Cycle at Index 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1 (value 2)
Explanation: There is a cycle in the linked list, where tail connects to the second node (value 2).

Example 2 · Cycle at Head:

Input: head = [1,2], pos = 0
Output: tail connects to node index 0 (value 1)
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3 · No Cycle:

Input: head = [1], pos = -1
Output: no cycle (null)
Explanation: There is no cycle in the linked list.

Constraints:

  • The number of the nodes in the list is in the range [0, 10^4].
  • -10^5 <= Node.val <= 10^5
  • pos is -1 or a valid index in the linked-list.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand and derive the mathematical proof L = nC - k for cycle entry detection.
  • Implement the two-phase Floyd's cycle detection algorithm cleanly.
  • Handle non-cyclic edge cases gracefully with strict boundary checks.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Locating the exact entry point / starting node of a cycle in a linked list or state machine.
  • Strict constraint against modifying node contents or pointer targets.
  • O(1) memory requirement.

Algorithmic Decision Tree:

  • If extra memory is allowed, a Hash Set records visited node pointers and returns the first duplicate.
  • For optimal O(1) space, run Floyd's Phase 1 to find meeting point, then Phase 2 to find cycle entry.

Connected Patterns:

Linked List CycleFind the Duplicate Number (Floyd's on Array)Intersection of Two Linked Lists

1. Brute Force — Hash Set Visited Node Tracking

Intuition

Traverse the list and insert each node address into a hash set. The first node that is already in the set is the exact entry point of the cycle.

Algorithm

  1. Step 1: Create an empty HashSet of node pointers.
  2. Step 2: Initialize curr = head.
  3. Step 3: While curr != null:
  4. a. If set.contains(curr), return curr (cycle entry).
  5. b. Add curr to set.
  6. c. Advance curr = curr.next.
  7. Step 4: Return null (no cycle).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <unordered_set>
3
4using namespace std;
5
6struct ListNode {
7 int val;
8 ListNode *next;
9 ListNode(int x) : val(x), next(nullptr) {}
10};
11
12class Solution {
13public:
14 ListNode *detectCycle(ListNode *head) {
15 unordered_set<ListNode*> visited;
16 ListNode* curr = head;
17 while (curr) {
18 if (visited.count(curr)) {
19 return curr;
20 }
21 visited.insert(curr);
22 curr = curr->next;
23 }
24 return nullptr;
25 }
26};
27
28int main() {
29 ListNode* n1 = new ListNode(3);
30 ListNode* n2 = new ListNode(2);
31 ListNode* n3 = new ListNode(0);
32 ListNode* n4 = new ListNode(-4);
33 n1->next = n2; n2->next = n3; n3->next = n4; n4->next = n2;
34
35 Solution sol;
36 ListNode* entry = sol.detectCycle(n1);
37 cout << "Brute Force Entry: " << (entry ? to_string(entry->val) : "null") << endl;
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(N) — Visits each node once in O(N). Hash set queries and insertions take O(1) average time.
  • Space complexity: O(N) — Allocates a hash set storing up to N node pointer addresses.

Why Brute Force Doesn't Scale:

Hash sets allocate auxiliary buckets and trigger cache evictions.

For N = 10,000, Floyd's 2-phase algorithm executes in <0.08ms.

2. Better — Count Cycle Length C & Align Pointers by C Steps

Intuition

After finding collision point with Floyd's algorithm, keep one pointer fixed and walk the second pointer around the cycle until it returns to the meeting point, counting the cycle length C. Then, place pointer p1 at head and p2 at head + C steps ahead. Advance both at 1x speed. Because p2 is exactly one full cycle ahead, they will meet at the cycle entry node.

Algorithm

  1. Step 1: Use slow (1x) and fast (2x) to find collision node meet.
  2. Step 2: If no collision, return null.
  3. Step 3: Count cycle length C: start curr = meet.next, C = 1; while curr != meet, curr = curr.next, C++.
  4. Step 4: Set p1 = head and p2 = head. Advance p2 by C steps.
  5. Step 5: While p1 != p2, advance p1 = p1.next and p2 = p2.next.
  6. Step 6: Return p1 (the cycle entry node).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5struct ListNode {
6 int val;
7 ListNode *next;
8 ListNode(int x) : val(x), next(nullptr) {}
9};
10
11class Solution {
12public:
13 ListNode *detectCycle(ListNode *head) {
14 if (!head || !head->next) return nullptr;
15
16 ListNode* slow = head;
17 ListNode* fast = head;
18 bool hasCycle = false;
19
20 while (fast && fast->next) {
21 slow = slow->next;
22 fast = fast->next->next;
23 if (slow == fast) {
24 hasCycle = true;
25 break;
26 }
27 }
28
29 if (!hasCycle) return nullptr;
30
31 // Count cycle length C
32 int C = 1;
33 ListNode* temp = slow->next;
34 while (temp != slow) {
35 C++;
36 temp = temp->next;
37 }
38
39 // Align pointers
40 ListNode* p1 = head;
41 ListNode* p2 = head;
42 for (int i = 0; i < C; ++i) {
43 p2 = p2->next;
44 }
45
46 while (p1 != p2) {
47 p1 = p1->next;
48 p2 = p2->next;
49 }
50
51 return p1;
52 }
53};
54
55int main() {
56 ListNode* n1 = new ListNode(3);
57 ListNode* n2 = new ListNode(2);
58 ListNode* n3 = new ListNode(0);
59 ListNode* n4 = new ListNode(-4);
60 n1->next = n2; n2->next = n3; n3->next = n4; n4->next = n2;
61
62 Solution sol;
63 ListNode* entry = sol.detectCycle(n1);
64 cout << "Better Offset Entry: " << (entry ? to_string(entry->val) : "null") << endl;
65 return 0;
66}

Time & Space Complexity

  • Time complexity: O(N) — Detects collision in O(N), counts cycle length C in O(C), advances pointer by C in O(C), and finds entry in O(N). Strict O(N) total time.
  • Space complexity: O(1) — Operates strictly in-place with O(1) auxiliary variables.

3. Optimal — Floyd's Phase 2 Pointer Derivation (Direct Entry Collision)

Intuition

Let distance to entry = L, distance inside loop to collision = k, loop size = C. When they collide, fast has traveled 2 * slow distance: 2(L + k) = L + mC + k => L = mC - k = (m-1)C + (C - k). This means starting one pointer at head and one at the collision point, both moving 1 step at a time, will meet at the exact cycle entry node!

Algorithm

  1. Step 1: If head == null || head.next == null, return null.
  2. Step 2: Initialize slow = head and fast = head.
  3. Step 3: While fast != null && fast.next != null:
  4. a. slow = slow.next.
  5. b. fast = fast.next.next.
  6. c. If slow == fast: break (collision found).
  7. Step 4: If fast == null || fast.next == null, return null (no cycle).
  8. Step 5: Set slow = head.
  9. Step 6: While slow != fast:
  10. a. slow = slow.next.
  11. b. fast = fast.next.
  12. Step 7: Return slow (the cycle entry node).

Linked List Cycle II Master Trace

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Reset slow to head (3)
Visual state
Values and pointers at this exact step
linked list
slow == fast → -4
Node 3
3
Node 2
2 (entry)
Node 0
0
Node -4
-4
NULL
Check / comparison
Collision found
Decision / next transition
Begin Phase 2
Why this step matters

Reset slow to head (3). Keep fast at -4.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5struct ListNode {
6 int val;
7 ListNode *next;
8 ListNode(int x) : val(x), next(nullptr) {}
9};
10
11class Solution {
12public:
13 ListNode *detectCycle(ListNode *head) {
14 if (!head || !head->next) return nullptr;
15
16 ListNode* slow = head;
17 ListNode* fast = head;
18 bool hasCycle = false;
19
20 while (fast && fast->next) {
21 slow = slow->next;
22 fast = fast->next->next;
23 if (slow == fast) {
24 hasCycle = true;
25 break;
26 }
27 }
28
29 if (!hasCycle) return nullptr;
30
31 slow = head;
32 while (slow != fast) {
33 slow = slow->next;
34 fast = fast->next;
35 }
36
37 return slow;
38 }
39};
40
41int main() {
42 ListNode* n1 = new ListNode(3);
43 ListNode* n2 = new ListNode(2);
44 ListNode* n3 = new ListNode(0);
45 ListNode* n4 = new ListNode(-4);
46 n1->next = n2; n2->next = n3; n3->next = n4; n4->next = n2;
47
48 Solution sol;
49 ListNode* entry = sol.detectCycle(n1);
50 cout << "Optimal Phase 2 Entry: " << (entry ? to_string(entry->val) : "null") << endl;
51 return 0;
52}

Time & Space Complexity

  • Time complexity: O(N) — Phase 1 collision occurs in at most N steps. Phase 2 requires L <= N steps. Total time is strictly O(N).
  • Space complexity: O(1) — Requires only two pointer variables with zero heap allocations.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Hash Set Node TrackingO(N)O(N)Traverse the linked list while recording each node reference in a Hash Set. The first node already present in the set is returned as the cycle entry. If null is reached, return null.O(N) memory allocation.
2.Better — Reverse List from Meeting PointO(N)O(1)Detect cycle with Floyd's algorithm. Reverse the list from the head to the collision point and count steps from both ends.Unnecessary pointer reversal complexity.
3.Optimal — Floyd's Algorithm 2-Phase Collision DerivationOptimalO(N)O(1)Phase 1: Find collision point with slow (1x) and fast (2x). Phase 2: Reset p1 = head and p2 = collision. Advance both at 1x speed. They meet at the cycle entry node.Optimal.

Common Pitfalls & Crucial Edge Cases

Moving fast pointer by 2 in Phase 2

In Phase 2, BOTH pointers must move at exactly 1x speed.

Not checking if cycle exists before Phase 2

If fast reaches null, exiting without checking hasCycle causes infinite loops.

Comparing values instead of pointers

slow.val == fast.val may trigger on distinct duplicate values.

Crucial Edge Cases to Validate:

  • No Cycle — fast reaches null -> returns null.
  • Cycle Begins at Head — head = [1, 2], pos = 0 -> Phase 1 meets at node 2, Phase 2 immediately aligns at node 1.
  • Single Node Self-Cycle — head = [1], pos = 0 -> Phase 1 meets at node 1, returns node 1.
  • Single Node No Cycle — head = [1], pos = -1 -> returns null.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Write out the equation clearly: 2 * (L + k) = L + mC + k => L = mC - k.
  2. Highlight that Phase 2 advances both pointers at 1 step per iteration.
  3. Mention how the exact same principle is applied in 'Find the Duplicate Number' on arrays.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.In the algebraic derivation L = (m - 1)C + (C - k), what does C - k represent?

2.At what speed should both pointers move during Phase 2?

3.What happens if there is no cycle in the linked list?

Back to DSA Sheet