题解 | #链表中环的入口结点#

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
  ListNode* EntryNodeOfLoop(ListNode* pHead) {
    // 空处理
    if (pHead == nullptr || pHead->next == nullptr) {
      return nullptr;
    } 

    // 分别定义快慢指针
    ListNode* low = pHead;
    ListNode* high = pHead;
    
    // 循环内部处理退出
    while (1) {
      // 慢指针一次走一步
      // 因为慢指针不肯呢比快指针先抵达nullptr故不需要这一个判断
      // if (low == nullptr) {
      //   break;
      // }
      low = low->next;
  
      // 快指针一次走两步 
      // 为防止崩溃(即访问nullptr)故判断high以及high->next
      if (high == nullptr || high->next == nullptr) {
        break;
      }
      high = high->next->next;
  
      // 若无环则快指针永远比慢指针先到达nullptr
      // 责low == high只能是成环
      if (low == high) {
        // 成环后将low(或high这里指定low)指向链表头 high留在原地
        // 改为每次移动一个节点则再次相遇时节点即为环的入口
        low = pHead;
        while (low != high) {
          low = low->next;
          high = high->next;
        }
        return low;
      }
    } 
      return nullptr;
  }
};