141. Linked List Cycle
Asked at Oracle, NVIDIA
Difficulty
Easy
Time
O(n)
Space
O(1)
Pattern
Hash Table
Companies
2
Problem
You are given the head of a singly linked list. Each node has a next pointer. Your job is to decide whether the list contains a cycle.
A cycle exists when some node can be reached again by repeatedly following next. In other words, the tail does not point to null — it points back to an earlier node. The position where the tail reconnects is called pos, but pos is not given to you as input; it is only used to describe the test data.
Return true if the list has a cycle, and false if it does not. The follow-up asks for a solution that uses O(1) extra memory, so you cannot just store every node you have seen.
A cycle means the tail points back
Constraints
- ●
The number of nodes is in the range [0, 10^4]. - ●
-10^5 <= Node.val <= 10^5 - ●
pos is -1 or a valid index in the linked list.
Examples
head = [3,2,0,-4], pos = 1truehead = [1,2], pos = 0truehead = [1], pos = -1falseAsked At
2 companies| Company | Difficulty | |
|---|---|---|
| Oracle | Easy | View all Oracle questions → |
| NVIDIA | Easy | View all NVIDIA questions → |
How to Think About It
A hash set can store every visited node, and if you encounter a node already in the set, a cycle exists.
This uses O(n) space which is acceptable but not optimal.
Floyd's Cycle Detection algorithm uses two pointers moving at different speeds.
The slow pointer moves one step and the fast pointer moves two steps each iteration.
If a cycle exists, the fast and slow pointers will eventually meet. If the fast pointer reaches null, there is no cycle.
Optimal Approach
Use Floyd's Cycle Finding Algorithm with two pointers. The slow pointer advances one node at a time while the fast pointer advances two nodes at a time. If there is no cycle, the fast pointer will reach null. If there is a cycle, the two pointers will eventually meet inside the cycle. This approach uses O(n) time and O(1) space.
Floyd's tortoise and hare
What Trips People Up in Real Interviews
Mention the hash table approach first as it is intuitive, then optimize with Floyd's algorithm.
Clearly explain why the two-pointer approach works — if there is a cycle, they must meet.
Discuss time and space complexity: O(n) time and O(1) space for Floyd's algorithm.
Clarify that detecting the cycle is different from finding the cycle start node.
Edge cases: empty list, single node with no cycle, single node pointing to itself.
Solution Code
O(n) timedef hasCycle(head):
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return FalseFrequently Asked Questions
What is the Linked List Cycle problem?
Given head, the head of a linked list, determine if the linked list has a cycle in it. A cycle exists if some node in the list can be reached again by continuously following the next pointer.
How do you solve Linked List Cycle?
The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Linked List Cycle?
Linked List Cycle is asked at Oracle, NVIDIA. It is a easy difficulty problem.
What are common mistakes on Linked List Cycle?
- Mention the hash table approach first as it is intuitive, then optimize with Floyd's algorithm.
- Clearly explain why the two-pointer approach works — if there is a cycle, they must meet.
- Discuss time and space complexity: O(n) time and O(1) space for Floyd's algorithm.
- Clarify that detecting the cycle is different from finding the cycle start node.
- Edge cases: empty list, single node with no cycle, single node pointing to itself.