leetcode:チェーンテーブルのリングの入口ノード
タイトル://チェーンテーブルを1つあげて、もしその中にリングが含まれているならば、そのチェーンテーブルのリングの入り口の接点を見つけてください、さもなくばnullを出力します.
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */
構想:高速ポインタ、高速ポインタは毎回2つの長さを前進し、遅いポインタは毎回1つの長さを前進し、リングが存在すれば、必ずリング内で出会う.始点からリング入口までの長さa、リング入口から出会い点までの長さb、出会い点からリング入口までの長さc、リング長さrを仮定すると、2(a+b)=a+b+nr a+b=nr a+r-c=nr a=c+(n-1)rの関係があるので、リングが存在する場合、2つのポインタをそれぞれ出会い点とヘッドから出発させ、出会い点をリング入口とする
コード:
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */
構想:高速ポインタ、高速ポインタは毎回2つの長さを前進し、遅いポインタは毎回1つの長さを前進し、リングが存在すれば、必ずリング内で出会う.始点からリング入口までの長さa、リング入口から出会い点までの長さb、出会い点からリング入口までの長さc、リング長さrを仮定すると、2(a+b)=a+b+nr a+b=nr a+r-c=nr a=c+(n-1)rの関係があるので、リングが存在する場合、2つのポインタをそれぞれ出会い点とヘッドから出発させ、出会い点をリング入口とする
コード:
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
if(NULL == pHead || NULL == pHead->next)
{
return NULL;
}
ListNode * slow = pHead;
ListNode * fast = pHead;
while(NULL != fast && NULL != fast->next)
{
fast = fast->next->next;
slow = slow->next;
if (fast == slow)
{
return GetEntryNodeOfLoop(fast, pHead);
}
}
return NULL;
}
ListNode* GetEntryNodeOfLoop(ListNode* fast, ListNode* pHead)
{
while(fast != pHead)
{
fast = fast->next;
pHead = pHead->next;
}
return fast;
}
};