Detect Loop in linked list

Time: O(n)

Space: O(1)

Intuition

Floyd's cycle detection: slow pointer moves one step, fast moves two. If they meet, a cycle exists. If fast reaches null, no cycle.

Algorithm

1slow = fast = head.
2While fast != null and fast.next != null: slow = slow.next. fast = fast.next.next.
3If slow == fast: return true (cycle). Return false.

Example Walkthrough

Input: 1â†’2â†’3â†’4â†’5â†’(back to 3)

1.Step 1: slow=2, fast=3. Step 2: slow=3, fast=5. Step 3: slow=4, fast=4. Meet at 4. Cycle!

Output: true

Common Pitfalls

•Check fast != null AND fast.next != null before each step to avoid NullPointerException.

Detect Loop in linked list.java

Java

// Approach: Floyd's cycle detection (fast/slow pointers). If they meet, a cycle exists.
// Time: O(n) Space: O(1)
class Node {
    int data;
    Node next;

    Node(int d) {
        data = d;
        next = null;
    }
}

class Solution {
    // Function to check if the linked list has a loop.
    public static boolean detectLoop(Node head) {
        Node slow = head;
        Node fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast)
                return true;
        }
        return false;
    }
}

Was this solution helpful?