Log inSign up
easyLeetCodeNot Started

Linked List Cycle

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

Linked List
Solve on LeetCode
Lesson

Problem Statement

Given head, the head of a linked list, determine if the linked list has a cycle in it.

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. Note that `pos` is not passed as a parameter.

Return true *if there is a cycle in the linked list*. Otherwise, return false.

Example 1 · Cycle Present:

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

Example 2 · 2-Node Cycle:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3 · No Cycle:

Input: head = [1], pos = -1
Output: false
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:

  • Master Floyd's Cycle-Finding Algorithm and its mathematical convergence proof.
  • Understand why relative speed difference of 1 guarantees collision without skipping.
  • Write boundary checks (fast && fast->next) to avoid NullPointerExceptions.

Pattern Recognition Trigger

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

Signals to Look For:

  • Infinite loop / cycle detection in a unidirectional pointer structure.
  • O(1) memory constraint prohibiting hash sets or node marking.
  • Meeting point / relative velocity questions.

Algorithmic Decision Tree:

  • If extra memory is allowed, a Hash Set of visited pointers detects cycles trivially.
  • If strict O(1) space is required, Fast and Slow pointers moving at 2x and 1x speed is optimal.

Connected Patterns:

Linked List Cycle II (Find Entry Node)Find the Duplicate Number (Floyd's on Array)Happy Number

1. Brute Force — Hash Set Visited Pointers

Intuition

Iterate through the list and record visited node references in a hash set. If the current pointer is already in the set, we have looped back, indicating a cycle.

Algorithm

  1. Step 1: Create an empty HashSet of ListNode*.
  2. Step 2: Initialize curr = head.
  3. Step 3: While curr != null:
  4. a. If set.contains(curr), return true.
  5. b. Add curr to set.
  6. c. Advance curr = curr.next.
  7. Step 4: If curr == null, return false.
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 bool hasCycle(ListNode *head) {
15 unordered_set<ListNode*> visited;
16 ListNode* curr = head;
17 while (curr) {
18 if (visited.count(curr)) {
19 return true;
20 }
21 visited.insert(curr);
22 curr = curr->next;
23 }
24 return false;
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; // cycle
34
35 Solution sol;
36 cout << "Brute Force hasCycle: " << (sol.hasCycle(n1) ? "true" : "false") << endl;
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(N) — Visits each node at most once before finding a duplicate or hitting null. Hash set insert and lookup take O(1) average time.
  • Space complexity: O(N) — Stores up to N node references in the hash set.

Why Brute Force Doesn't Scale:

Hash set allocations cause cache misses and trigger GC pressure on large graphs.

For N = 10,000 nodes, Floyd's pointer loop runs in ~0.05ms with 0 heap bytes allocated.

2. Better — Node Redirection to Sentinel Dummy

Intuition

As we visit each node, save its next pointer, and then redirect its next pointer to point to a unique sentinel node dummy. If we ever visit a node whose next pointer already points to dummy, we have encountered a cycle.

Algorithm

  1. Step 1: Create a single sentinel dummy = new ListNode(0).
  2. Step 2: curr = head.
  3. Step 3: While curr != null:
  4. a. If curr.next == dummy, return true.
  5. b. Save nextTemp = curr.next.
  6. c. Point curr.next = dummy.
  7. d. Advance curr = nextTemp.
  8. Step 4: Return false.
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 bool hasCycle(ListNode *head) {
14 ListNode* dummy = new ListNode(0);
15 ListNode* curr = head;
16
17 while (curr != nullptr) {
18 if (curr->next == dummy) {
19 delete dummy;
20 return true;
21 }
22 ListNode* nextTemp = curr->next;
23 curr->next = dummy;
24 curr = nextTemp;
25 }
26
27 delete dummy;
28 return false;
29 }
30};
31
32int main() {
33 ListNode* n1 = new ListNode(1);
34 ListNode* n2 = new ListNode(2);
35 n1->next = n2; n2->next = n1; // cycle
36
37 Solution sol;
38 cout << "Better Sentinel hasCycle: " << (sol.hasCycle(n1) ? "true" : "false") << endl;
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(N) — Visits each node once in O(N) time.
  • Space complexity: O(1) — Uses single static sentinel dummy pointer in O(1) space.

3. Optimal — Floyd's Tortoise and Hare (Fast & Slow Pointers)

Intuition

Initialize slow = head and fast = head. Move slow by 1 step (slow = slow.next) and fast by 2 steps (fast = fast.next.next). If fast or fast.next is null, there is no cycle (return false). If slow == fast, they have met in the cycle (return true).

Algorithm

  1. Step 1: If head == null || head.next == null, return false.
  2. Step 2: Initialize slow = head and fast = head.
  3. Step 3: While fast != null && fast.next != null:
  4. a. Advance slow = slow.next.
  5. b. Advance fast = fast.next.next.
  6. c. If slow == fast, return true.
  7. Step 4: Return false (fast reached end of list).

Linked List Cycle Master Trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
No collision yet
Visual state
Values and pointers at this exact step
linked list
slow → 2fast → 0
Node 3
3
Node 2
2
Node 0
0
Node -4
-4
NULL
Check / comparison
2 != 0
Decision / next transition
Keep moving
Why this step matters

No collision yet.

Step 1 / 3
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 bool hasCycle(ListNode *head) {
14 if (!head || !head->next) return false;
15
16 ListNode* slow = head;
17 ListNode* fast = head;
18
19 while (fast && fast->next) {
20 slow = slow->next;
21 fast = fast->next->next;
22 if (slow == fast) {
23 return true;
24 }
25 }
26
27 return false;
28 }
29};
30
31int main() {
32 ListNode* n1 = new ListNode(3);
33 ListNode* n2 = new ListNode(2);
34 ListNode* n3 = new ListNode(0);
35 ListNode* n4 = new ListNode(-4);
36 n1->next = n2; n2->next = n3; n3->next = n4; n4->next = n2;
37
38 Solution sol;
39 cout << "Optimal hasCycle: " << (sol.hasCycle(n1) ? "true" : "false") << endl;
40 return 0;
41}

Time & Space Complexity

  • Time complexity: O(N) — If no cycle, fast pointer reaches null in N/2 steps. If a cycle of length C exists, fast catches slow in at most N steps. Total time is strictly O(N).
  • Space complexity: O(1) — Uses only two pointers (slow and fast), requiring O(1) auxiliary memory.

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 Visited Node TrackingO(N)O(N)Traverse the list node by node. Store each node's memory address in a Hash Set. If the current node already exists in the set, a cycle is detected. If null is reached, no cycle exists.Memory allocation for hash set.
2.Better — In-Place Node Value Sentinel MarkingO(N)O(1)Traverse the list and overwrite each visited node's value or next pointer with a special sentinel value (e.g. 1000001 or point curr.next = dummySentinel). If a node already contains the sentinel, a cycle exists.Destructive data mutation.
3.Optimal — Floyd's Tortoise and Hare (Fast & Slow Pointers)OptimalO(N)O(1)Move slow by 1 node (slow = slow.next) and fast by 2 nodes (fast = fast.next.next). If fast or fast.next is null, return false. If slow == fast, return true.Optimal.

Common Pitfalls & Crucial Edge Cases

Missing the `fast.next != null` condition

Checking only fast != null will throw a NullPointerException when accessing fast.next.next on odd-length lists.

Advancing before checking

Initializing slow = head.next and fast = head.next.next without guarding against single-node lists.

Modifying node data when prohibited

In production, altering node values or pointer targets can corrupt concurrent readers.

Crucial Edge Cases to Validate:

  • Empty List — head = null -> false immediately.
  • Single Node No Cycle — head = [1] -> fast.next == null -> false.
  • Single Node Self-Cycle — head = [1], pos = 0 -> fast.next.next == head -> true on iteration 1.
  • Two Nodes with Cycle — head = [1, 2], pos = 0 -> slow == fast on iteration 2.

Interview Tips & Best Practices

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

  1. State the relative velocity intuition immediately: 'Inside the loop, fast gains on slow by 1 node per step, so it is impossible for fast to jump over slow.'
  2. Point out the necessary loop guard: while (fast != null && fast.next != null).
  3. Transition naturally to Linked List Cycle II by explaining how finding the collision point allows mathematical deduction of the cycle entry node.

Quick Comprehension Check

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

1.Why is the fast pointer guaranteed to meet the slow pointer if a cycle exists?

2.What is the worst-case time complexity of Floyd's Cycle Detection algorithm?

3.What happens if we move the fast pointer 3 steps instead of 2?

Back to DSA Sheet