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

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。

解法：

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

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

View Code

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;
  }

View Code

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-cycle-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。