链表中环的入口结点

题目描述:给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

刚看到这道题，想着用HashSet，但这毕竟是算法题，应尽量避免使用工具类；HashSet解法：

public ListNode EntryNodeOfLoop(ListNode pHead) {

      HashSet<ListNode> hashSet = new HashSet<>();
      while (pHead != null){
          if (hashSet.contains(pHead)) {
              return pHead;
          }else {
              hashSet.add(pHead);
              pHead = pHead.next;
          }
      }

      return null;
  }

然后看题解，看到了这个链接

• https://blog.nowcoder.net/n/1a2aba61b69441578c99d40bbb3ccc6d?f=comment

思路：

• 创建快慢指针，slow、fast，如果有环，快慢指针总有指向同一个节点的时候，设置标记；否则当快指针等于null的时候，也就停止了；

• 判断标记，如果为false，返回null；否则，进行下一步；

• 计算环的长度；

• 使快指针先移动一个环的长度，然后快慢指针同时移动，直到快慢指针相等，该节点即环的入口节点；

  public ListNode EntryNodeOfLoop(ListNode pHead) {
  
    ListNode slow = pHead;
    ListNode fast = pHead;
    boolean flag = false;
    // 判断是否有环
    while (fast != null && fast.next != null){
  
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast){
            flag = true;
            break;
        }
    }
    // 没有环直接返回null
    if (!flag) return null;
  
    // 有环, 计算出环的长度
    ListNode workNode = slow;
    int count = 1;
    workNode = workNode.next;
    // slow对应节点开始计数1，直到workNode==slow，计数完成
    while (workNode != slow){
        count++;
        workNode = workNode.next;
    }
  
    slow = pHead;
    fast = pHead;
    //移动一个环的长度
    for (int i = 0; i < count; i++) {
        fast = fast.next;
    }
    // 快慢指针同时移动，直到相等
    while (slow != fast){
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
  }