IT会社100題-7-2つのチェーンテーブルが交差しているかどうかを判断する

問題の説明:
ループ、すなわちノードのnextがチェーンテーブルの前のノードを指し、チェーンテーブルの末尾にループを形成する単一のチェーンテーブルがある. 

チェーンテーブルがこのようなチェーンテーブルであるかどうかをどのように判断しますか? 

問題の拡張:

チェーンテーブルにリングがある可能性がありますか?

2 2 2つのチェーンテーブルが交差する最初のノードを求める必要がある場合は? 

問題の分析:
ループがない場合、2つのチェーンテーブルにノードが同じであれば、次のノードも同じであり、テールノードも同じである. 
では、2つのチェーンテーブルの終端点が同じかどうかを判断します.(O(len1+len2))

//if there is no cycle
boolean isJoinedSimple(Node n1, Node n2){
   while(n1 != null)
      n1 = n1.next;
   while(n2 != null)
      n2 = n2.next;
   return n1 == n2;
}

拡張1:
まずループがあるかどうかを判断する必要があります.このようにして、2つのポインタを定義して、頭のノードを指して、1つは1つのノードを移動するたびに、もう1つは2つのノードを移動して、遅いのは速い(つまり2つのポインタが再会する)に追いつくことができれば、ループがあることを説明します.

boolean hasLoop(Node n){
   Node nFast = n;
   Node nSlow = n;
   while(nFast != null && nSlow != null){
      nFast = nFast.next.next;
      nSlow = nSlow.next;
      if(nFast == nSlow)
         return true;
   }
   return false;
}

2つのチェーンテーブルのリング入口は、以下の方法でそれぞれ見つかった.まず、スナップポインタp_を設定します.fastとp_slow、2つのポインタが交差する点を見つけて、p_inter.そしてpはチェーンテーブルから始まり、p_slowはp_からinterが歩き始め、毎回1歩歩くと、2つのポインタが交差する場所がチェーンテーブルの入り口です.
(a)AとBの2つのチェーンテーブルの入口をそれぞれ求め,同じであれば.2つのチェーンテーブルが交差する最初のノードメソッドは同じで,ループをNULLとするだけでよい.
(b)2つのチェーンテーブルのリング入口が異なる場合、最初の交差ノードはない.
拡張2:
エントリポイントを見つけるには:
fastがslowと出会うと、slowはチェーンテーブルを遍歴していないに違いないが、fastはリング内でnリングを循環している(1<=n).slowがsステップを歩いたと仮定すると、fastは2 sステップ(fastステップ数はsにリングを多回転するnリングを加えたものにも等しい)を歩いて、リング長をrとすると、2 s=s+nrs=nrはチェーンテーブル全体の長さLを設定し、入口リングと出会い点の距離をxとし、始点からリング入口点までの距離をaとする.a+x=nra+x=(n−1)r+r=(n−1)r+L−aa=(n−1)r+(L−a−x)(L−a−x)は、出会い点からループ入口点までの距離であることから、チェーンテーブルヘッドからループ入口点まで(n−1)サイクル内ループ+出会い点からループ入口点までであることが分かる.そこで、チェーンテーブルヘッド、出会い点からそれぞれ1つのポインタを設け、各ステップずつ歩くたびに、2つのポインタが必ず出会う.そして出会った最初の点は環入口点です.プログラムの説明は以下の通りです.

Node findLoopPort(LinkedList lst){
   Node nFast = lst.head;
   Node nSlow = lst.head;

   while(nFast != null && nFast.next!= null){
      nFast = nFast.next.next;
      nSlow = nSlow.next;
      if(nFast == nSlow) break;
   }

   if(nFast == null || nSlow == null)
      return null;

   nSlow = head;
   while(nSlow != nFast){
      nSlow = nSlow.next;
      nFast = nFast.next;
   }

   return nSlow;
}