LeetEye LeetEye
Medium Linked List ~5 min

Linked List Cycle

linked-list linked-list-cycle

Problem

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer.

Return true if there is a cycle in the linked list. Otherwise, return false.

Examples

Example 1
Input: head = [3,2,0,-4], pos = 1
Output: true
Tail connects to node at index 1 (0-indexed).
Example 2
Input: head = [1,2], pos = 0
Output: true
Tail connects to node at index 0.
Example 3
Input: head = [1], pos = -1
Output: false
No cycle.
Key Insight

Fast and slow pointers: if there's a cycle, they will eventually meet.

Slow moves 1, fast moves 2. If cycle exists, fast catches slow. If no cycle, fast reaches null.

How to Approach This Problem

Pattern Recognition: When you see keywords like linked list cycle linked-list, think Linked List.

Step-by-Step Reasoning

1 To detect a cycle, we could:
Answer: Store visited nodes in a set and check for repeats
If we see the same node twice, there's a cycle. But this uses O(n) space.
2 If fast moves 2x speed of slow, in a cycle:
Answer: Fast will eventually catch slow
In a cycle, fast gains 1 position on slow each step. Eventually the gap closes to 0.
3 If slow is at position S and fast is at position F in a cycle:
Answer: The gap decreases by 1 each step
Fast moves 2, slow moves 1. Relative movement = 1. Gap shrinks by 1.
4 If there's no cycle:
Answer: Fast reaches null first
Fast moves faster, so it hits the end of the list first (or fast.next is null).
5 We continue the loop while:
Answer: fast is not null AND fast.next is not null
Fast moves 2 steps, so we need both fast and fast.next to exist.
6 If slow == fast during traversal:
Answer: There is definitely a cycle
For them to meet, fast must have gone around and caught up. Only possible in a cycle.

Solution

def hasCycle(head: ListNode) -> bool:
    slow = fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
        if slow == fast:
            return True
    
    return False

Complexity Analysis

Time O(n)
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice Linked List problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye