Course4all
Join us on telegram
Home/dsa/Linked List Patterns/Linked List Cycle

Linked List Cycle

Master this topic with zero to advance depth.

Linked List Cycle

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

List: 3 -> 2 -> 0 -> -4 -> 2... (Cycle) 1. Slow=3, Fast=2 2. Slow=2, Fast=-4 3. Slow=0, Fast=0 (MEET!) Result: true
Easy

Examples

Input: head = [3,2,0,-4], pos = 1
Output: true

There is a cycle where tail connects to the second node.

Approach 1

Level I: HashSet / Visited Set

Intuition

The simplest way to detect a cycle is to keep track of all nodes seen. If we encounter a node that's already in our 'visited' set, it means there's a cycle.

Visual Trace

List: 3 -> 2 -> 0 -> -4 (points back to 2) Iter 1: node=3, Set={3} Iter 2: node=2, Set={3, 2} Iter 3: node=0, Set={3, 2, 0} Iter 4: node=-4, Set={3, 2, 0, -4} Iter 5: node=2, Found in Set! Cycle detected.
  1. Initialize an empty HashSet of node references.
  2. Traverse the list. For each node, check if it exists in the set.
  3. If yes, return true. Otherwise, add the node to the set and move to next node.
⏱ O(N)💾 O(N)

Detailed Dry Run

Input: 3 -> 2 -> 0 -> -4 -> 2 (cycle)

  1. Seen: {3}
  2. Seen: {3, 2}
  3. Seen: {3, 2, 0}
  4. Seen: {3, 2, 0, -4}
  5. Next is 2. 2 is in Seen. Cycle detected!
java
public boolean hasCycle(ListNode head) {
    Set<ListNode> seen = new HashSet<>();
    while (head != null) {
        if (seen.contains(head)) return true;
        seen.add(head);
        head = head.next;
    }
    return false;
}

⚠️ Common Pitfalls & Tips

O(N) space is often not allowed if O(1) is possible.

Approach 2

Level II: Node Marking

Intuition

If we can modify the list, we can point all seen nodes toward a sentinel 'Visited' node. If a node's next already points to this sentinel, we've closed the circle.

Visual Trace

Nodes: [A] -> [B] -> [C] -> [B(cycle)] 1. At [A]: Save next [B], set [A].next = Sentinel. Move to [B]. 2. At [B]: Save next [C], set [B].next = Sentinel. Move to [C]. 3. At [C]: Save next [B], set [C].next = Sentinel. Move to [B]. 4. At [B]: [B].next is already Sentinel! return true.
⏱ O(N)💾 O(1)

Detailed Dry Run

1 -> 2 -> 1. Point 1.next to dummy. Point 2.next to dummy. 2.next is already dummy? No, 1.next was dummy. When we go from 2 to 1, 1.next is already dummy.

java
public boolean hasCycle(ListNode head) {
    ListNode dummy = new ListNode(0);
    while (head != null) {
        if (head.next == dummy) return true;
        ListNode next = head.next;
        head.next = dummy;
        head = next;
    }
    return false;
}

⚠️ Common Pitfalls & Tips

This destroys the original list.

Approach 3

Level III: Floyd's Cycle Finding (Tortoise and Hare)

Intuition

Use two pointers, slow and fast. slow moves one step, fast moves two. If there's a cycle, the fast pointer will eventually 'lap' the slow pointer.

Visual Trace

List: 1 -> 2 -> 3 -> 4 -> 5 -> (back to 2) Start: S=1, F=1 Step 1: S=2, F=3 Step 2: S=3, F=5 Step 3: S=4, F=3 (F wrapped around cycle) Step 4: S=5, F=5 (MEET!)
⏱ O(N)💾 O(1)

Detailed Dry Run

Input: 1 -> 2 -> 1...

  • Initial: slow=1, fast=2.
  • Step 1: slow = slow.next (2), fast = fast.next.next (2).
  • Match! Return true.
java
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
}

⚠️ Common Pitfalls & Tips

Check both fast and fast.next for null to avoid errors.

← Previous QuestionCount Complete Subarrays in an Array
Next Question →Remove Nth Node From End of List