0

リンクされたリストの交点のノードを見つける方法は?

     A1-->A2-->A3-->A4-->A5-->A6-->A7
                         ^
                         |
               B1-->B2-->B3
  1. A と B は 2 つの連結された連結リストです
  2. A1、A2...A7 および B1..B3 は、リストのノードです。
  3. リスト A と B は A5 で交差します。

交差点のノードを見つける必要があります

4

2 に答える 2

2

解決策 1:

リスト内のすべてのノードについて、次のノードが他のリストのノードと同じかどうかを確認します。

   if(A->next == B->next)
   {
      //nodes of interaction
   }

これは m*n の複雑さを持ちます

解決策 2 (効率的):

  • 両方のリストの長さを見つけます (それぞれ L1 と L2)。
  • 長さの絶対差 [abs(L1-L2)] を見つけます。
  • 前の差分から取得したノードに移動します。
  • ここで、A->next が B->next と同じかどうかのチェックを開始します
于 2013-11-08T06:44:05.230 に答える