How to Solve Detect Loop in Linked List on LeetCode
Detect Loop in Linked List (Cycle Detection) is a fundamental problem that tests your understanding of pointer manipulation.
Problem Statement
Given the head of a linked list, determine if the linked list has a cycle in it. Return true if there is a cycle, else false.
Example:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: The tail connects to the node at position 1 (cycle exists).
Why This Problem Matters for Interviews
- Tests pointer logic and linked list fundamentals
- Introduces fast/slow pointer (tortoise and hare) concepts
- Core building block for many linked list challenges
Approach to Detect Loop in Linked List
Fast and Slow Pointer (Floyd’s Cycle Detection)
Move two pointers at different speeds; if they meet, there’s a cycle.
Time Complexity: O(n)
Space Complexity: O(1)
def hasCycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
Key Interview Talking Points
- Why a set/visited approach is O(n) space
- How fast and slow pointers work
- What to do if you need the cycle’s starting node
Big O Complexity Recap
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Fast/Slow Pointer | O(n) | O(1) |
Pro Interview Tips
- Draw examples with and without cycles
- Mention possible infinite loops without cycle checks
- Practice follow-ups (find start of cycle, cycle length)