LinkedListCycleII.java

/**
 * Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
 *
 * <p>Follow up: Can you solve it without using extra space?
 */
public class LinkedListCycleII {
 public ListNode detectCycle(ListNode head) {
 if (head == null) return head;
 ListNode fast = head, slow = head;
 do {
 if (fast.next != null && fast.next.next != null) {
 fast = fast.next.next;
 slow = slow.next;
 } else {
 return null;
 }
 } while (fast != slow);
 slow = head;
 while (fast != slow) {
 fast = fast.next;
 slow = slow.next;
 }
 return fast;
 }
}