The challenge
Determine whether following next pointers ever revisits a node.
Compare node identity, not equal values. Do not modify any links.
Example
1 → 2 → 3 → 4 → node 2 contains a cycle.
Use the walkthrough below to inspect the input and each state change.
See Detect cycle, step by step
Follow the pointers. Watch each link change.
A1Inspect node links
| Node | Value | Next |
|---|---|---|
| A1 | 1 | A2 |
| A2 | 2 | A3 |
| A3 | 3 | A4 |
| A4 | 4 | A2 |
Read the input
IDs label node objects. Equal values can belong to different nodes. Solid arrows are next links; dashed arrows are random links.
Start from the input head pointers.View original input
A: 1 (A1) → 2 (A2) → 3 (A3) → 4 (A4); parameters: {"cycleAt":1}
Parameter indices are zero-based, except n from the end, which is one-based. Node IDs remain fixed when links change.
Put it into code
Inside a cycle, fast gains one position per iteration and must meet slow.
Node stores val and next; the random-pointer lesson adds random. C++ uses C++17 or later.
class Node:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
#include <cstddef>
struct Node {
int val;
Node* next;
Node(int value = 0, Node* link = nullptr)
: val(value), next(link) {}
};
bool has_cycle(Node* head) {
Node* slow = head;
Node* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}