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

/*
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;
    if (pHead->next == pHead) return pHead;

    auto meeting_node = MeetingNode(pHead);
    if (meeting_node == nullptr) return nullptr;

    auto loop_len = GetLoopLen(meeting_node);
    return GetLoopHead(pHead, loop_len);
  }

  ListNode* GetLoopHead(ListNode* phead, int offset_count) {
    ListNode* fast = phead;
    while (offset_count != 0) { 
      fast = fast->next;
      --offset_count;
    }

    auto slow = phead;
    while (slow != fast) {
      slow = slow->next;
      fast = fast->next;
    }

    return slow;
  }

  size_t GetLoopLen(ListNode* meeting_node) {
    auto loop_len = 1;
    auto p = meeting_node->next;
    while (p != meeting_node) {
      ++loop_len;
      p = p->next;
    }
    return loop_len;
  }

  ListNode* MeetingNode(ListNode* head) {
    auto slow = head;
    auto fast = head->next;
    while (fast != nullptr && fast->next != nullptr) {
      slow = slow->next;
      fast = fast->next->next;
      if (slow == fast)
        return slow;
    }
    return nullptr;
  }
};