CareerCup_2.6 - Find Cycle Start

LoopStartFinder.java

package Chapter2;

public class LoopStartFinder {
    public static <T> Node<T> findLoopStart(MyLinkedList<T> list) {
	if (list == null || list.head == null || list.head.next == null)
	    return null;
	Node<T> fir = list.head.next.next;
	Node<T> sec = list.head.next;

	//first time meet use runner tech
	while (fir != null && sec != null) {
	    if (fir == sec) {
		break;
	    }
	    if (fir.next == null)
		return null;
	    fir = fir.next.next;
	    sec = sec.next;
	}

	fir = list.head;
	//second time meet
	while (fir != sec) {
	    fir = fir.next;
	    sec = sec.next;
	}

	return fir;
    }

    public static void main(String[] args) {
	Node<String> cycleHead = new Node<String>("A", new Node<String>("B",
		new Node<String>("C", new Node<>("D", new Node<>("E", null)))));
	MyLinkedList<String> list = new MyLinkedList<String>(cycleHead);
	list.last().next = list.head.next.next;
	Node<String> loopStart = findLoopStart(list);
	System.out.println("loop start is " + loopStart.data);
    }
}