题目描述：

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

 

思路分析：

这道题首先需要判断链表是否存在环，很快就能想到用快慢指针来判断。

由于快慢指针的相遇位置并不一定为链表环的入口结点，需要进一步判断。这里参考了一个博客 https://www.cnblogs.com/likeio/p/3593686.html ，由于快指针和慢指针相遇时，快指针一定比慢指针多走了n（n=1, 2, ...)个环，可以通过列对应关系得知，在已知有环的情况下，两个指针分别以头结点和相遇结点为起点，步长为1前进，一定会在环的入口结点相遇。

需要注意是，在找入口结点时，首先需要判断头结点和相遇结点是否相等，再进行后续判断，否则对于头结点即为入口结点的情况会遗漏。

 

代码：

1 /* 2 struct ListNode { 3     int val; 4     struct ListNode *next; 5     ListNode(int x) : 6         val(x), next(NULL) { 7     } 8 }; 9 */10 class Solution {11 public:12     ListNode* EntryNodeOfLoop(ListNode* pHead)13     {14         if(pHead==nullptr)15             return nullptr;16         ListNode* walker;17         ListNode* runner;18         walker = pHead;19         runner = pHead;20         while(walker!=nullptr && runner!=nullptr)21         {22             walker = walker->next;23             if(runner->next==nullptr)24                 return nullptr;25             else26                 runner = runner->next->next;27             if(runner==walker)28                 break;29         }30         if(walker == runner)31         {32             walker = pHead;33             while(walker!=nullptr && runner!=nullptr)34             {35                 if(runner==walker)36                     break;37                 walker = walker->next;38                 runner = runner->next;39             }40             if(walker==runner)41                 return walker;42             else43                 return nullptr;44         }45         else46             return nullptr;47     }48 };