leetcode LinkedListCycleII
z
 2019-04-09 10:36:27   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import utils.ListNode;

public class LinkedListCycleII {
  /**
   * Given a linked list, return the node where the cycle begins.
   * If there is no cycle, return null.
   *
   * To represent a cycle in the given linked list,
   * we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to.
   * If pos is -1, then there is no cycle in the linked list.
   *
   * Note: Do not modify the linked list.
   */
  public ListNode detectCycle(ListNode head) {
    if (head == null || head.next == null) return null;
    ListNode slow = head;
    ListNode fast = head;

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