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[thesameCasearlier] Output:C

CC150-2.6.java

/**
 * 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
 * Output:C
 * 
 * @Runtime & spaces
 * runtime: O(n)
 * space:   O(1)
*/
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Main so = new Main();
		ListNode a = new ListNode(1);
		ListNode b = new ListNode(2);
		ListNode c = new ListNode(3);
		ListNode d = new ListNode(4);
		ListNode e = new ListNode(5);
		ListNode f = new ListNode(6);
		ListNode g = new ListNode(7);
		a.next = b;
		b.next = c;
		c.next = d;
		d.next = e;
		e.next = f;
		f.next = e;
		g.next=c;
		System.out.println(so.findLoopStart(a).val);
	}

	public ListNode findLoopStart(ListNode head) {
		if (head == null)
			return null;
		ListNode fast = head;
		ListNode slow = head;
		while (fast != null && fast.next != null) {
			fast = fast.next.next;
			slow = slow.next;
			if (slow == fast)
				break;
		}
		/* there's no loop in the list */
		if (fast == null || fast.next == null)
			return null;

		slow = head;
		while (slow != fast) {
			slow = slow.next;
			fast = fast.next;
		}
		return fast;
	}
}