### 思路:先[判斷是否有環](http://www.hmoore.net/persuez/algorithm/858057),無環返回 nullptr,有環則有以下方法:記相遇點為pos,然后同時從鏈頭和pos點出發,它們的相遇點即為環的入口點。證明如下:設從鏈頭到環入口點(連接點)的步數為 x(包括兩個端點x + 1個節點),連接點到相遇點的步數為 y,慢指針走了 s 步,那么s = x + y,快指針走了2s = x + n * t + y(n 為走環的圈數,t 為環中步數(從連接點出發回到連接點),得到 x + y = nt,所以同時從鏈頭和pos點出發,它們的相遇點即為環的入口點。實現代碼如下:
```
// meetingNode函數在之前的對應章節有,思路中有鏈接可以跳轉過去
SList* findEntryForLoop(SList *list)
{
if (list == nullptr) {
return nullptr;
}
SList *meetingNode = meetingNode(list);
if (meetingNode == nullptr) {
return nullptr;
}
// 循環直至相遇,通過以上證明,循環一定會結束
while (list != meetingNode) {
list = list->m_next;
meetingNode = meetingNode->m_next;
}
return list;
}
```