How to detect a loop in a linked list?

How to Detect a Loop in a Linked List

Detecting a loop in a linked list is a common problem in computer science. One of the most efficient algorithms to solve this problem is Floyd’s Cycle-Finding Algorithm, also known as the "Tortoise and the Hare" algorithm. This algorithm uses two pointers at different speeds to detect a loop.

Floyd’s Cycle-Finding Algorithm (Tortoise and Hare)

Algorithm Steps

1. Initialize two pointers:

   • slow pointer, which moves one step at a time.
   • fast pointer, which moves two steps at a time.

2. Move the pointers:

   • Move the slow pointer one step forward.
   • Move the fast pointer two steps forward.

3. Check for a loop:

   • If the slow pointer and fast pointer meet, there is a loop.
   • If the fast pointer reaches the end (i.e., null), there is no loop.

Implementation in Java

Here is a Java implementation of Floyd’s Cycle-Finding Algorithm:

class ListNode {
    int value;
    ListNode next;

    ListNode(int value) {
        this.value = value;
        this.next = null;
    }
}

public class LinkedListLoopDetector {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }

        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;       // Move slow pointer one step
            fast = fast.next.next;  // Move fast pointer two steps

            if (slow == fast) {     // Check if the pointers meet
                return true;
            }
        }

        return false;  // No loop found
    }

    public static void main(String[] args) {
        // Creating a linked list with a loop for testing
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = head.next;  // Creating a loop

        LinkedListLoopDetector detector = new LinkedListLoopDetector();
        if (detector.hasCycle(head)) {
            System.out.println("The linked list has a loop.");
        } else {
            System.out.println("The linked list does not have a loop.");
        }
    }
}

Explanation

1. ListNode Class:

   • Represents a node in the linked list.
   • Contains a value and a reference to the next node.

2. hasCycle Method:

   • Initializes two pointers, slow and fast.
   • Moves slow one step and fast two steps in each iteration.
   • Checks if the two pointers meet, indicating a loop.
   • Returns true if a loop is detected and false otherwise.

3. Main Method:

   • Demonstrates the creation of a linked list with a loop.
   • Uses the hasCycle method to detect the loop and prints the result.

Alternative Method: Using a HashSet

Another way to detect a loop in a linked list is by using a HashSet to keep track of visited nodes. If a node is visited twice, there is a loop.

Implementation in Java

import java.util.HashSet;

public class LinkedListLoopDetectorWithHashSet {
    public boolean hasCycle(ListNode head) {
        HashSet<ListNode> visitedNodes = new HashSet<>();

        ListNode current = head;
        while (current != null) {
            if (visitedNodes.contains(current)) {
                return true;  // Loop detected
            }
            visitedNodes.add(current);
            current = current.next;
        }

        return false;  // No loop found
    }

    public static void main(String[] args) {
        // Creating a linked list with a loop for testing
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = head.next;  // Creating a loop

        LinkedListLoopDetectorWithHashSet detector = new LinkedListLoopDetectorWithHashSet();
        if (detector.hasCycle(head)) {
            System.out.println("The linked list has a loop.");
        } else {
            System.out.println("The linked list does not have a loop.");
        }
    }
}

Summary

• Floyd’s Cycle-Finding Algorithm (Tortoise and Hare):

  • Uses two pointers moving at different speeds.
  • Efficient with O(n) time complexity and O(1) space complexity.

• HashSet Method:

  • Uses a HashSet to track visited nodes.
  • Simpler but uses O(n) extra space.

Both methods effectively detect loops in a linked list, and the choice of method can depend on specific constraints or preferences. For more in-depth knowledge and practical examples on linked lists and other data structures, consider exploring Grokking the Coding Interview on DesignGurus.io, which provides comprehensive courses on essential coding and interview techniques.