判断环形链表并给出入环口的节点位置

  public static class ListNode {
    private int val;
    private ListNode next;

    public ListNode(int val) {
      this.val = val;
    }
  }

public static ListNode detectCycle(ListNode head) {
    /*定义一个快指针，每次走2步*/
    ListNode fast = head;
    /*定义一个慢指针，每次走1步*/
    ListNode slow = head;
    /*标识是否有环*/
    boolean haveCycle = false;
    /*让2个指针第一次相遇*/
    while (fast != null && fast.next != null) {
      slow = slow.next;
      fast = fast.next.next;
      if (slow == fast) {
        haveCycle = true;
        break;
      }
    }
    /*如果有环，进行下一步判断*/
    if (haveCycle) {
      /*快指针重新指向头节点*/
      fast = head;
      /*此时slow和fast都每次只走一步，当2个指针相遇时，必然是在环的入口点，直接返回*/
      while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
      }
      /*证明：
      1.假设从头节点到入环口之间是a个节点（不包含入环那个节点），环中的节点数是b；
      2.第一次相遇时slow走了s步，fast走了f步 f=2s，f=s+nb,2个公式计算后得到 s=nb  f=2nb；
      3.由此我们得出结论是slow走的步数是环中节点的整数倍，所以此时我们把fast节点重新指向头节点，当fast走a步时，slow会走a+nb步，所以最后2个相遇时必定在a的时候*/
      return slow;
    }
    return null;
  }