C2P6.java

package chapter2;

public class C2P6 {

  /*
	 * p1: slower pointer which moves 1 step each time, p2: faster pointer which moves 2 steps each time
	 * k: number of steps from the head to the node, n:the number of steps taken when two pointers meets
	 * l: number of steps in the loop
	 * p1 and p2 start at the head, when they first meet, we have 2n - k - (n - k) = l --> n = l
	 * thus, they meet in the position where is l - k steps from the corrupt node(i.e. k steps to the corrupt node)
	 * so if we let p1 start from the head, and p2 start from this position, both with the same speed which is 1 step each time
	 * they shall take k more steps to meet each other at the corrupt node
	 * 
	 * time:O(n) space:O(1)
	 */
	public static Node findCorruptedNode(Node head){
		Node p1, p2;
		p1 = p2 = head;
		do {
			p1 = p1.next;
			p2 = p2.next.next;
		} while (p1 != p2);
		p1 = head;
		do {
			p1 = p1.next;
			p2 = p2.next;
		} while (p1 != p2);
		return p1;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int array[] = {1,2,3,4,5};
		Node head = new Node(array);
		head.next.next.next.next = head.next.next;
		System.out.println(findCorruptedNode(head));
	}

}