參考資料：
[1]本頁思路
關(guān)鍵詞：
2x=x+n
鏈表有環(huán)，長啥樣：
一個鏈表中包含環(huán)
思路：
第一個寝杖，找環(huán)中相匯點(diǎn)。有兩個指針分別指向頭結(jié)點(diǎn)p1互纯、p2瑟幕。p1每次移動一步，p2每次移動兩步留潦。直到他們相匯p1=p2只盹。比如他們相匯于5。p2實際上比p1多走了一個環(huán)兔院，設(shè)p1走了x,則p2走了2x,環(huán)中的節(jié)點(diǎn)數(shù)為n殖卑，則x+n=2x。所以p1實際上走了一個環(huán)坊萝。
第二個孵稽，找環(huán)中的入口節(jié)點(diǎn)。p1保持保持位置不變十偶。p2回到鏈表的起點(diǎn)∑邢剩現(xiàn)在p1和p2每次都走一步,直到p1=p2。那么此時p1為入口節(jié)點(diǎn)惦积。
疑問：
注意需要判斷鏈表是否包含環(huán)
自己的代碼:
再次改進(jìn)版：
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
//如為空節(jié)點(diǎn)或者是一個節(jié)點(diǎn)的話接校，那么返回空節(jié)點(diǎn)
if(pHead == nullptr || pHead->next == nullptr)
return nullptr;
ListNode* pNode1 = pHead;
ListNode* pNode2 =pHead;
do {
pNode1= pNode1->next;
pNode2= pNode2->next->next;
}while((pNode1 !=pNode2) && (pNode1 != nullptr) && (pNode2 != nullptr) && (pNode2->next !=nullptr));
//判斷是否是有環(huán)
if((pNode1 == nullptr) || (pNode2 == nullptr) ||(pNode2->next == nullptr))
return nullptr;
pNode1=pHead;
while(pNode1 != pNode2)
{
pNode1 = pNode1->next;
pNode2 = pNode2->next;
}
return pNode1;
}
};
