cc150_2.6

gistfile1.java

package cc150;

import java.util.Hashtable;

/*
 * 2.6 Given a circular linked list, implement an algorithm which returns the node at
the beginning of the loop.
DEFINITION
Circular linked list: A (corrupt) linked list in which a node's next pointer points
to an earlier node, so as to make a loop in the linked list.
EXAMPLE
Input: A - > B - > C - > D - > E - > C [the same C as earlier]
Output: C
Algorithm 
I hate the solution from  book :(   here is  mine :

Assume the   node  data is unique for the simplify,  we also can add  a "key" as the unique flag
 1. user fast and  slow pointer find  a  the   circle and get  the collide spot , 
 2. use hashtable  to  store all the  nodes of circle
 3. traverse the list from the head,  get the first one that exist in hashtable.
 
 O(n) and O(n)
 */
public class FindCircle_2_6 {

	public static void main(String[] args) {
		CircleNode root= new CircleNode();
		root.data =  2;
		CircleNode current = root;
		CircleNode newNode = new CircleNode();
		newNode.data = 9 ;
		current.next = newNode;
		current = current.next;
		
		newNode = new CircleNode();
		newNode.data = 5 ;
		current.next = newNode;
		current = current.next;

		newNode = new CircleNode();
		newNode.data = 3 ;
		current.next = newNode;
		current = current.next;
		CircleNode thecirclespot = newNode;
	
		newNode = new CircleNode();
		newNode.data =  6;
		current.next = newNode;
		current = current.next;
		
		newNode = new CircleNode();
		newNode.data =  8;
		current.next = newNode;
		current = current.next;
		
		newNode = new CircleNode();
		newNode.data =  1;
		current.next = newNode;
		current = current.next;
		
		newNode = new CircleNode();
		newNode.data =  7;
		current.next = newNode;
		current.next = thecirclespot;
		
		CircleNode collideSpot = findCircle(root);
		
		if(collideSpot == null)
			System.out.println("There is no  circle");
		else{
			CircleNode circleStartNode = getstartNode(root,collideSpot);
			System.out.println("the circle start node  is " +circleStartNode.data );
		}
		
	}

	private static CircleNode getstartNode(CircleNode root, CircleNode collideSpot) {
		Hashtable circledNodeTable = new Hashtable();
		circledNodeTable.put(collideSpot.data, true);
		CircleNode runner = collideSpot.next;
		while(runner.data!=collideSpot.data){
			circledNodeTable.put(runner.data,true);
			runner= runner.next;
		}
		runner = root;
		while(runner!= null){
			if(circledNodeTable.containsKey(runner.data))
				return runner;
			runner= runner.next;
		}
		return null;
	}

	private static CircleNode findCircle(CircleNode root) {
		if(root == null || root.next == null )
			return null;
		CircleNode slow = root;
		CircleNode fast = root.next;
		while(slow!=null  && fast!=null && slow.data != fast.data){
			slow = slow.next;
			if(fast.next!= null)
				fast = fast.next.next;
			else
				fast =fast.next;
		}
		if(slow==null  || fast==null)
			return null;
		else
			return fast;
	}

}
class CircleNode {
	int data;
	CircleNode next;
	public CircleNode(){
	}
}