Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
when fast meets slow, move slow to the head and the cycle starting node is the node where slow meets fast again.
public ListNode detectCycle(ListNode head) {
if (head==null) {
return null;
}
ListNode current = head;
ListNode fast = head;
while (fast.next!=null && fast.next.next!=null) {
current = current.next;
fast = fast.next.next;
//there is a loop
if (current==fast) {
break;
}
}
//no loop
if (fast.next==null || fast.next.next==null) {
return null;
}
current = head;
while (current != fast) {
current = current.next;
fast = fast.next;
}
return current;
}