Determine whether a singly linked list contains a cycle.
Problem
You are given the head of a singly linked list. Determine whether the list contains a cycle.
A cycle exists if, while following next pointers, you can revisit the same node again. A node may point to a previous node in the list, causing traversal to loop forever.
Return true if a cycle exists, otherwise return false.
Notes
- You must inspect the list by following node links.
- The list may be empty.
- A node is identified by its reference, not by its value.
Input Format
- A singly linked list is provided through its head node.
- Each node contains an integer value and a
nextpointer. - The structure may or may not contain a cycle.
Output Format
- Return a boolean value:
trueif the linked list has a cyclefalseotherwise
Constraints
- The list length is finite, but traversal may repeat if a cycle exists.
- Node values are not guaranteed to be unique.
- Aim for linear time and constant extra space if possible.
Example 1
Input
head = [3,2,0,-4], pos = 1
Output
true
Explanation
The tail connects back to the node at index 1, so the list loops forever.
Example 2
Input
head = [1,2], pos = 0
Output
true
Explanation
The last node points back to the first node, creating a cycle.
Show 1 more example
Example 3
Input
head = [1], pos = -1
Output
false
Explanation
The single node does not point back to itself, so there is no cycle.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.