Find Loop in a Linked List

While traversing a linked list, when we reach already visited node again it is considered to be a loop in a linked list. We can't reach end of the linked list in case linked list has a loop.
Following diagram shows a linked list with loop. In this diagram, node 6 points back to node 3 which was already visited:

There are various ways to solve this problem:
1. Using HashSet
2. Tortoise Hare algorithm

1. Using HashSet: 

    While traversing the linked list, we insert the node in a HashSet. Every time we visit a node, we check if this node exists in the HashSet. if HashSet already contains this node that means we are visiting this node second time and that proves a cycle in the linked list. Time Complexity of searching in a HashSet is O(1), so time complexity of this algorithm remains O(n) only but it requires O(n) of additional space as well. For a linked list with huge number of nodes, this algorithm is not recommended due to memory requirements.

2. Using Tortoise Hare Algorithm:

This is also known as Floyd's cycle finding algorithm. This is a pointer algorithm that uses only two pointers, which move through the sequence at different speeds. The algorithm is named after Robert W. Floyd, who was credited with its invention by Donald Knuth. 

Following diagram illustrates this algorithm:

In this algorithm, we maintain two pointers - one is slow pointer and another is fast pointer. Slow pointer is analogy for tortoise and fast pointer is analogous to a hare, that's why algorithm has this name. We start from head node towards the tail. Slow pointer moves one node at a time whereas fast pointer moves two nodes at a time. If there is no loop/cycle in the list, these pointer would never meet. But in case of a cycle, these pointers meet on some node. If these pointers meet it proves a cycle in the list else there is no cycle in the list.

Java Solution:

In this program, we have used three element linked list having nodes 1, 2 and 3. Node 3 points back to node 2.

public class DetectCycle {

    private static void detectLoop(LinkedList.Node head) {
        LinkedList.Node slow = head;
        LinkedList.Node fast = head;

        if (head.next == null) {
            System.out.println("Empty List");
        }

        while (fast != null && slow != null) {
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            }
            if (slow == fast) {
                System.out.println("Cycle found in the list");
                return;
            }
        }
        System.out.println("No Cycle found in the list");
    }

    public static void main(String[] args) {
        LinkedList.Node list = getLinkedList();
        detectLoop(list);
    }

    private static LinkedList.Node getLinkedList() {
        LinkedList.Node dummy = new LinkedList.Node(-9999);
        LinkedList.Node head = dummy;
        LinkedList.Node node1 = new LinkedList.Node(1);
        head.next = node1;
        head = head.next;
        LinkedList.Node node2 = new LinkedList.Node(2);
        head.next = node2;
        head = head.next;
        LinkedList.Node node3 = new LinkedList.Node(3);
        node3.next = node2;
        head.next = node3;
        return dummy.next;
    }

    static class LinkedList {
        Node head;

        public static class Node {
            int data;
            Node next;

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