CC150_2_6.java

/*
Created by bitcpf
*/

package cc150_2_6;

import java.util.LinkedList;

public class CircleDetect {
	
	public static Node DetectCL(Node head){
		Node fast_pt = head;
		Node slow_pt = head;
		int flag = 0;
		while(fast_pt != null && fast_pt.next != null){

			slow_pt = slow_pt.next;
			fast_pt = fast_pt.next.next;
			flag ++;

			if(fast_pt == slow_pt){
				break;
			}
		}
		fast_pt = head;
		while(fast_pt != slow_pt){
			fast_pt = fast_pt.next;
			slow_pt = slow_pt.next;
		}

		return slow_pt;
	}
	public static void printlist(Node hd){
		
		while(hd.next != null && !(hd.item.toString().equals("stop"))){
			System.out.print(hd.item + " ");
			hd = hd.next;
		}
		System.out.println(hd.item);
	}
	
	public static void main(String[] args){
		Node head = new Node("a");
		Node temp;
		Node current = head;
		for(int i= 1; i < 18; i++){
			temp = new Node((char) ('a'+i));
			current.next = temp;
			current = temp;
		}
		Node tail = current;
		tail.item = "stop";
		// Build the circle
		temp = head;
		for(int i = 0; i < 5; i++){
			temp = temp.next;
			
		}
		tail.next = temp;
		
		printlist(head);
		System.out.println("Circle head is: "+temp.item);
		System.out.println("Result is: " + DetectCL(head).item);
		
	}
}