Linked List Cycle
Asked at Oracle
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Oracle | EASY | View all Oracle 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.
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
def 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Linked List Cycle?
Linked List Cycle is asked at Oracle. 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.