Detecting Loop in a Linked List and Identify the Start of the Loop

DetectLoopInLinkedList.java

/* File:    DetectLoopInLinkedList.java
 * Created: 2018-05-09
 * Author:  Sabbir Manandhar
 *
 * Copyright (c) 2018 Hogwart
 */

import java.util.HashSet;
import java.util.Set;

/**
 * Detect Loop in a Linked List
 *
 * @author Sabbir Manandhar
 * @version 1.0
 */
public class DetectLoopInLinkedList {

  public static void main(String[] args) {
    DetectLoopInLinkedList detectLoopInLinkedList = new DetectLoopInLinkedList();
    int i = 1;
    Node head = detectLoopInLinkedList.new Node(i++);
    Node tail = head;
    tail.next = detectLoopInLinkedList.new Node(i++);
    tail = tail.next;
    tail.next = detectLoopInLinkedList.new Node(i++);
    tail = tail.next;
    tail.next = detectLoopInLinkedList.new Node(i++);
    tail = tail.next;
    tail.next = detectLoopInLinkedList.new Node(i++);
    tail = tail.next;
    tail.next = detectLoopInLinkedList.new Node(i++);
    tail = tail.next;
    tail.next = detectLoopInLinkedList.new Node(i++);
    tail = tail.next;
    tail.next = detectLoopInLinkedList.new Node(i++);
    tail = tail.next;
    tail.next = detectLoopInLinkedList.new Node(i++);
    tail = tail.next;
    tail.next = detectLoopInLinkedList.new Node(i++);
    tail = tail.next;
    tail.next = detectLoopInLinkedList.new Node(i++); // 11
    tail = tail.next;
    Node loopBegin = tail;
    tail.next = detectLoopInLinkedList.new Node(i++);
    tail = tail.next;
    tail.next = detectLoopInLinkedList.new Node(i++);
    tail = tail.next;
    tail.next = detectLoopInLinkedList.new Node(i++);
    tail = tail.next;
    tail.next = detectLoopInLinkedList.new Node(i++);
    tail = tail.next;
    tail.next = detectLoopInLinkedList.new Node(i++);
    tail = tail.next;
    tail.next = detectLoopInLinkedList.new Node(i++);
    tail = tail.next;
    tail.next = detectLoopInLinkedList.new Node(i++);
    tail = tail.next;
    tail.next = detectLoopInLinkedList.new Node(i++);
    tail = tail.next;
    tail.next = detectLoopInLinkedList.new Node(i++);

    // No Loop
    Node loopStart1 = detectLoopInLinkedList.detectLoop(head);
    Node loopStart2 = detectLoopInLinkedList.detectLoopFloydMethod(head);
    System.out.println(loopStart1 == null && loopStart2 == null ? "SUCCESS: Loop Not Found" : "Failure");

    // Crate Loop at 11
    tail = tail.next;
    tail.next = loopBegin;

    loopStart1 = detectLoopInLinkedList.detectLoop(head);
    loopStart2 = detectLoopInLinkedList.detectLoopFloydMethod(head);
    System.out.println(loopStart1 == loopStart2 ? "SUCCESS: Loop Start Found: " + loopStart1.value : "Failure");
  } // main

  //-----------------------------------------------------------------------------------

  /**
   * Detects a loop in a given LinkedList
   * Based upon keeping track of already visited Nodes
   * @param head head of the LinkedList
   * @return start of loop if it exists, otherwise null
   */
  public Node detectLoop(Node head) {
    Set<Node> visitedNodes = new HashSet<Node>();

    Node node = head;
    while (node != null) {
      if (visitedNodes.contains(node)) { // loop detected. node is the start of the loop
        return node;
      } else {
        visitedNodes.add(node);
        node = node.next;
      }
    }

    return null; // no loop
  } // detectLoop

  //------------------------------------------------------------------------------------

  /**
   * Detect Loop in a LinkedList using Floyd's Method
   * @param head Head of the LinkedList
   * @return start of loop if it exists, otherwise null
   */
  public Node detectLoopFloydMethod(Node head) {
    Node faster = head;
    Node slower = head;

    // detect loop
    while (faster != null && faster.next != null) {
      faster = faster.next.next;
      slower = slower.next;

      if (faster == slower) { // loop detected
        break;
      }
    }

    if (faster != slower) return null; // loop not detected

    // detect start of loop
    faster = head;
    while (faster != slower) {
      faster = faster.next;
      slower = slower.next;
    }

    return faster;
  } // detectLoopFloydMethod


  //------------------------------------------------------------------------------------

  /**
   * Class to represent Linked List Node
   */
  public class Node {
    Node next;
    int value;

    public Node(int value) {
      this.value = value;
    } // Node
  } // Node

} // DetectLoopInLinkedList