チェーンテーブルのリングの入口ノード
1062 ワード
《剣指offer》ブラシノート3学習コンテンツチェーンテーブルのリングのエントリノード(1)考え方チェーンテーブルが1つの空のチェーンテーブルである場合、または1つのノードのみのチェーンテーブルである場合、答えはNULLである.チェーンテーブルが少なくとも2つのノードを有する線形チェーンテーブルである場合、答えもNULLである.チェーンテーブルにループが含まれている場合、入口ノードのアドレスは必ず現れ、2回しか現れない.特にチェーンテーブル全体がループである場合、入口ノードはこの単一チェーンテーブルの第1番目である1つのノード.チェーンテーブル全体に2回アドレスが表示されるノードを見つけます.構造体ノードのアドレスをキーワードとしてハッシュテーブルを使用できます.ここは既製のset容器を使っていて、素晴らしいです.setコンテナ使用参考:https://www.cnblogs.com/AndyJee/p/4705846.html(2)コード/*struct ListNode{int val;struct ListNode next;ListNode(int x):val(x)、next(NULL){};/class Solution { public: ListNode EntryNodeOfLoop(ListNode pHead) { if(pHeadNULL ||pHead->nextNULL)return NULL; 参考サイトhttps://cuijiahua.com/blog/2018/02/basis_67.html https://www.cnblogs.com/AndyJee/p/4705846.html
set Hash;
ListNode* pNode=pHead;
while(pNode!=NULL)
{
if(Hash.find(pNode)==Hash.end())
{
Hash.insert(pNode);
pNode=pNode->next;
}
else
{
return pNode;
}
}
return NULL;
}