// D. Scott
// CCI - Problem 2.8
// Determine whether a singly linked list contains a loop

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

    void appendToTail(int d) {
        Node end = new Node(d);
        Node n = this;
        while (n.next != null) {
            n = n.next;
        }
        n.next = end;
    }
}

public static void main (String[] args)
{
    // Generate list 
    Node list1 = new Node(5);
    Node head = list1;
    Node head1 = list1;
    list1.appendToTail(3);
    list1.appendToTail(8);
    list1.appendToTail(6);
    list1.appendToTail(2);
    list1.appendToTail(16);
    list1.appendToTail(33);
    list1.appendToTail(1);
    
    // Create loop in list
    while (list1.next.next != null) 
        list1 = list1.next;
    head1 = head1.next;
    head1= head1.next;
    head1 = head1.next;
    
    list1.next = head1;
    
    list1 = head;
    
    System.out.println("List: 5 3 8 6 2 16 33 6 (back to first 6) 1")

    // Create 2 pointers to interate through list
    Node p1 = list1.next;
    Node p2 = list1;

    // Move p1 sequentially 1,2,3,etc. nodes ahead of p2
    // until a collision detected
    for (int i = 1; i < 10; i++) {
        for (int j = 0; j < 15; j++) {
            if (p1.data == p2.data && p1.next == p2.next) {
                System.out.println("Found loop at node "+p1.data);
                System.exit(0);
            }
            int ct = 0;
            while (ct < i) {
                p1 = p1.next;
                ct++;
            }
            p2 = p2.next;
        }
        p1 = list1.next;
        p2 = list1;
    }
    System.out.println("No loop found in the list.");
    
}