Abstract / Summary

Determine if a linked list has a cycle by checking if any node is visited more than once.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 55% (9+ million submissions).

Typical patterns to solve this problem:

• Hash Table
• Linked List
• Two Pointers

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The presented function determines whether a singly-linked list contains a cycle. It follows a straightforward approach: it traverses the list while recording each visited node in a hash-based container. If a node is encountered that already exists in the container, a cycle is reported; otherwise the traversal reaches the end of the list and the function returns false. The implementation relies on the standard library’s unordered_set to achieve constant-time membership checks.

Core Logic

Initialization of the tracking container

At the start of the routine an empty hash set is created to store pointers to the nodes that have been seen so far.

unordered_set<ListNode*> seen;

The choice of a hash set provides rapid insertion and lookup, which is essential for keeping the traversal efficient even for long lists.

Iterative traversal

The function enters a loop that continues as long as the current pointer is not null. The loop condition directly reflects the natural end of a non-cyclic list.

while (head)
{
    // body omitted for clarity
}

Cycle detection

Inside the loop the first operation checks whether the current node pointer already resides in the seen set. The count method returns a non-zero value when the element is present, triggering an immediate return of true.

if (seen.count(head) > 0)
    return true;

This early-exit strategy prevents unnecessary processing once a cycle is identified.

Recording the node and advancing

If the node has not been seen, it is inserted into the set, and the pointer advances to the next element in the list.

seen.insert(head);
head = head->next;

The insertion step guarantees that any future encounter with the same node will be caught by the detection check.

Completion without a cycle

When the loop terminates because head becomes null, the function concludes that no cycle exists and returns false.

return false;

Edge Cases Handled

The algorithm gracefully manages several boundary conditions without additional code.

When the input list is empty (head is null), the loop body is never executed and the function returns false, correctly indicating the absence of a cycle.

A list consisting of a single node that does not point to itself also bypasses the detection condition, proceeds to the end, and yields false.

If a node’s next pointer references itself, the node is inserted into the set on the first iteration, and the subsequent iteration finds the same pointer already present, causing an immediate return of true.

These scenarios demonstrate that the implementation covers the full spectrum of minimal and degenerate list configurations.

Performance Optimizations Observed

The use of unordered_set provides average-case constant-time operations for both insertion and membership testing, which keeps the overall execution time proportional to the number of distinct nodes visited.

The early return upon detecting a repeated node eliminates further traversal, saving work in the presence of a cycle that appears early in the list.

By storing raw pointers rather than copying node contents, the memory footprint of each entry in the set remains minimal, and the insertion operation avoids costly deep copies.

The loop advances the pointer directly after insertion, ensuring that each node is processed exactly once in the non-cyclic case, which avoids redundant checks.

Overall, the design balances simplicity with effective use of standard library facilities to achieve a responsive solution for cycle detection.

Imagine you are walking along a path made of stepping stones, and each stone has a little arrow pointing to the next one. This code is like holding a magic scrapbook as you walk. Every time you step on a stone, you take a quick snapshot of it and glue it into your book.

As you move from one stone to the next, you pause for a second to check your scrapbook. You look through all the pages to see if you have already stepped on the stone you are currently standing on. If you find a picture of your current stone in the book, it means you have accidentally walked in a circle and ended up back where you started. If you find that page, you know for sure that the path is a loop. If you reach a stone that does not have an arrow pointing to anything else, you know the path ends and there is no loop to worry about.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java							TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java		C#	JS	Go			TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	begeekmyfriend				C
	BigEggStudy					C#
	black-shadows	C++
	bujosa								Rust
	chandansgowda		Python
	charles-wangkai			Java
	chenyanzhe	C++
	Dijkstra-Edu			Java
	DimitrisJim				C
	everthis						JS
	fartem									Ruby
	FelixFan1122					C#
	fengvyi	C++
	fpdjsns	C++
	gaosq0604		Python
	Garvit244		Python
	gouthampradhan			Java
	halfrost							Go
	haoel	C++
	JoshCrozier						JS
	keineahnung2345	C++
	Krazune				C
	lennylxx				C
	linouk23	C++
	lkwq007		Python
	luangong	C++
	muhammadfarhankt							Go
	pruthvikp		Python
	qiyuangong		Python
	shreymehul					C#
	sonugiri1043	C++
	suxrobGM					C#
	trung-hn		Python
	varunu28			Java
	vli02				C
	vthwang			Java
	wisdompeak	C++
	XiaotaoGuo	C++
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, JavaScript, Python, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Rust
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
Dijkstra-Edu	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fengvyi	C++
fpdjsns	C++
gaosq0604	Python
Garvit244	Python
gouthampradhan	Java
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
muhammadfarhankt	Go
pruthvikp	Python
qiyuangong	Python
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
vthwang	Java
wisdompeak	C++
XiaotaoGuo	C++
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality