/*
    It is possible for a linked list structure to contain loops.  Consider
the following scenario:

cell A = new cell(1,new cell(2,new cell(3,new cell(4,null))));
A.tail.tail.tail = A.tail;

Non of our algorithms will terminate for such a list!

We are going to write a program that detects if there are such cycles in
a cell structure. The key is to keep track of all the cells we've seen
in a separate data structure, so we can detect when something is a duplicate.

For this we need, in addition to the regular cell class, a "pcell" class,
that implements a list of pointers to cells.  That is, every "head" of
a pcell is a pointer to cell.  The pcell list contains all the cells
that we have already seen in a cell list, so we can detect cycles.

*/

class cell
{
    int head;
    cell tail;
    cell(int h, cell t) {head=h; tail=t;}

    // procedure to detect if a cell-list is cyclic.  It returns null
    // if it's not cyclic, or a pointer to the offending cell, that is,
    // a cell whose tail is a cell that already exists in the same list.
    // We want it in this form so we can "sever" loops using this procedure.
    public cell cyclic()
    {
	cell answer = null; // default (null means no cycles)
	pcell SEEN = new pcell(this,null); // initially, only this cell
	                                   // has been seen
        cell i = this;
	while (i.tail != null && answer==null)
        {
	    if (SEEN.member(i.tail))
		{ answer = i; }  // found "bad" cell, exit loop
	    else
                { SEEN = new pcell(i.tail,SEEN); } // add i to SEEN list
	    i=i.tail;
	} // while
	return answer;
    }// cyclic
     
} //cell

class pcell
{
    cell head;  // pcells contain pointers to cells
    pcell tail;
    pcell(cell h, pcell t) {head=h; tail=t;}

    public boolean member(cell A)  // determine if A is in pcell list
    {
	boolean answer = false;
	if (A==null) return false;
	pcell i = this;
	while (i!=null && !answer) 
	    {
		if (A==i.head) answer = true;
		i = i.tail;
	    }
	return answer;
    }
}//pcell


public class checklist
{
    public static void main(String[] args)
    {
     cell A = new cell(1,new cell(2,new cell(3,new cell(4,null))));
     A.tail.tail.tail = A.tail;  // create loop
     cell badcell = A.cyclic();
     System.out.println(badcell); // print address of cell
     if (badcell!=null) badcell.tail = null;  //  sever loop
     badcell = A.cyclic();
     System.out.println(badcell); // print address of cell (null)
    } // main
}


/*
   Finally, this algorithm runs in O(n*n) time complexity since there's a
   nested loop.  That is, each nth cell need to be checked against the n-1
   cells that came before it in order to determine if there's a duplicate.
*/