文章出處
粗暴方法，供出利器
文章列表
題目描述
一個鏈表中包含環，請找出該鏈表的環的入口結點。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
}
};粗暴方法，供出利器map:
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
if(pHead == NULL)
return NULL;
map<ListNode*, int> cnt;
while(pHead != NULL)
{
cnt[pHead]++;
if(cnt[pHead] == 2)
return pHead;
pHead = pHead->next;
}
return NULL;
}
};
燒腦解法：
- 第一步： 找環中相匯點。分別用p1，p2指向鏈表頭部，p1每次走一步，p2每次走二步，直到p1==p2找到在環中的相匯點。
- 第二步： 找環的入口。接上步，當p1==p2時，p2所經過節點數為2x, p1所經過節點數為x,設環中有r個節點, p2比p1多走 n (n >= 1)圈. 有2x=nr+x; 可以看出p1實際走了n個環的步數，再讓p2指向鏈表頭部，p1位置不變，p1,p2每次走一步直到p1==p2; 此時p1和 p2指向環的入口.
簡單證明：
設起點到相遇點距離為x，起點到入口點距離為y，環長度為r， 則快慢指針相遇時，滿足2x-x=nr，n為快指針在環中轉的圈數。于是 x=nr 快慢指針相遇點距環入口點距離 x-y(正負沒關系) 。相遇后，快指針從起點重新開始以步長為1速度開始走，經過距離y到達環入口點，慢指針走y步后距離環入口點距離為 x-y+y = x = nr，即走到了環入口點，兩個指針相遇！
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
if(pHead == NULL)
return NULL;
ListNode* fastPos = pHead;
ListNode* slowPos = pHead;
while(fastPos != NULL && slowPos != NULL)
{
if(fastPos->next != NULL)
{
fastPos = fastPos->next;
fastPos = fastPos->next;
}
else
return NULL;
slowPos = slowPos->next;
if(slowPos == fastPos)
break;
}
if(fastPos == NULL || slowPos == NULL)
return NULL;
fastPos = pHead;
while(fastPos != slowPos)
{
fastPos = fastPos->next;
slowPos = slowPos->next;
}
return fastPos;
}
};
文章列表
全站熱搜
留言列表
