1

Algo を使用して、Singly Link List の最後の 3 番目の要素を見つけようと考えています。自分で 1 つ考え出しました (スペースが効率的ではありません)
O(n) 時間の複雑さを持つループを使用して、ArrayList にリンク リストを配置します多くのスペースの複雑さ]
次に、Arraylist のサイズを見つけて、(size-2) インデックス位置で要素 [必要な要素] を取得します。

参考
までに他に調べたのは : 2 つのポインターを置き、1 番目のポインターを 1 番目の要素に、2 番目のポインターを 3 番目の要素に保持し、それらを平行に移動
する

4

7 に答える 7

6
  • 次の 2 つのポインターを使用pointer-1します。pointer-2

  • 単一の連結リストの 3 番目のノードを pointer-1指すようにします。

     pointer-1 = node1->next->next; // point to 3rd nd

 node1-->node2-->node3-->node4---> ...... -->node-last
                 ^
                 |
                pointer-1

  • pointer-2ポイントを最初のノードに設定します

     pointer-2 = node1;   // point to 1st nd

 node1-->node2-->node3-->node4---> ...... -->node-last
   ^              ^
   |              |
  pointer-2      pointer-1

  • ここで、最後のノードを指すまでループ内のリンクされたリストを移動し、ループ内pointer-1でポインター 2 も更新します (毎回、それ自体の次のノードまで)

    while (pointer-1->next!=NULL){// points to last node 
     pointer-1 = pointer-1 -> next;
     pointer-2 = pointer-2 -> next;
}

When loop ends pointer-1 points to last-node, pointer-2 points to third last

 node1-->node2-->........ ->node-l3-->node-l2-->node-last
                             ^                   ^
                             |                   |
                           pointer-2            pointer-1

これは O(n) 回で機能します。ここで、nはリンク リスト内のノードの数です。

于 2013-07-05T15:26:03.350 に答える
1

リンクされたリストは単独でリンクされているため、最初から最後までトラバースして 3 番目から最後の要素が何であるかを知る必要がありますO(n)(リンクされたリストの 3 番目から最後までの要素へのポインターを維持しない限り) 時間は避けられません)。

あなたの2つのポインタのアイデアは、一定のスペースを使用します。ArrayList を作成するとオーバーヘッドが増え、より多くのスペースを使用するため、これはおそらくより良いオプションです。

于 2013-07-05T15:21:42.000 に答える
0

O(n) であってもこれを解決する代替ビュー

空の配列 (n) を作成し、この配列へのポインタを 0 から開始し、同様にリンク リストの先頭から開始します。ノードにアクセスするたびに、それを配列の現在のインデックスに格納し、配列ポインターを進めます。配列のノードを埋め続け、配列の最後に到達したら、上書きするように最初からやり直してください。リストの最後の最後を終了すると、最後からn番目の要素のポインタになります:)

于 2013-07-05T15:33:27.740 に答える
0

実際には、JavaLinkedListはそのサイズを追跡するので、'list.get(list.size()-2)' に移動するだけで済みますが、構築されたリンク リストでは、次のようにします。

3 つの値の配列を保持します。リストをたどりながら、更新値を に追加しますarray[i%3]。値がなくなったら、 の値を返しますarray[(i-2)%3]。

于 2013-07-05T15:38:33.863 に答える
0

2 つのポインターを取得します。pA, pB pA を 3 要素進め、pB を先頭に移動:

1->2->3->4-> .... ->99->100 
|     |
pB    pA

この後、pA が最後の要素に到達するまで、同じループ内で両方のポインターを移動します。

その時点で pB は最後の 3 番目の要素を指します。

1->2->3->4-> .... ->98->99->100 
                    |        |
                    pB       pA

編集：トラバーサルは1つになります：

while(pA->next!=null){
   pA = pA->next;
   pB = pB->next;
}

ここでpBは最後から3番目になります

于 2013-07-05T15:23:16.757 に答える