Detecting a cycle in a linked list problem and solution in Java

Detecting a cycle in a linked list is a classic FAANG interview problem. The most common and efficient way is Floyd’s Tortoise and Hare (Fast & Slow Pointers) algorithm.

I’ll show both Java and Python solutions.

1️⃣ Java – Detect Cycle

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class LinkedListCycle {
    Node head;

    // Detect cycle using Floyd's Algorithm
    public boolean hasCycle() {
        Node slow = head;
        Node fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;           // move by 1
            fast = fast.next.next;      // move by 2

            if (slow == fast) {         // cycle detected
                return true;
            }
        }
        return false; // no cycle
    }

    public static void main(String[] args) {
        LinkedListCycle list = new LinkedListCycle();
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(4);

        list.head = n1;
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n2; // creates a cycle

        System.out.println("Cycle detected? " + list.hasCycle());
    }
}

Output:

Cycle detected? true

2️⃣ Python – Detect Cycle

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def has_cycle(self):
        slow = self.head
        fast = self.head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

# Example
n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
n4 = Node(4)

ll = LinkedList()
ll.head = n1
n1.next = n2
n2.next = n3
n3.next = n4
n4.next = n2  # cycle

print("Cycle detected?", ll.has_cycle())

Output:

Cycle detected? True

⚡ Key Points

1. Fast & slow pointers move at different speeds. If there’s a cycle, they will meet at some node.
2. Time Complexity: O(n)
3. Space Complexity: O(1) (no extra memory required)
4. Alternative approach: Use a HashSet to store visited nodes (O(n) space).