0

私はLinkedListの実装とその非常に新しい主題に取り組もうとしています。さまざまなタイプの LinkedList の問題に取り組んでいるときに、以前の要素を追跡するために LinkedList をトラバースするという一般的なエラーに直面しています。いくつかの昔ながらのトラバース方法は

リスト L = L.next

ここで問題が発生します。リスト内のいくつかの要素をスキップしてから、次の要素のセットを削除してから、再び問題をスキップしたいのと同じです。これを行うには、スキップするポイントまで LL をトラバースすることを考えましたが、トラバースすると L = L.next について考えるようになり、再び再帰に陥ります。

この問題の特徴と、この状況に対処する方法について少し説明してください。それを私の理解の障害と考えてください。それにより、これ以上先に進むことができません。ほんの少しの光が問題を解決するのに役立ちます。

私はこの種の実装は非常に新しいです

私のLinkedList-

        MyList list_Sort = new MyList(9);
        list_Sort.next = new MyList(8);
        list_Sort.next.next = new MyList(8);
        list_Sort.next.next.next = new MyList(7);
        list_Sort.next.next.next.next = new MyList(5);
        list_Sort.next.next.next.next.next = new MyList(4);
        list_Sort.next.next.next.next.next.next = new MyList(6);
        list_Sort.next.next.next.next.next.next.next = new MyList(3);
        list_Sort.next.next.next.next.next.next.next.next = new MyList(1);
        list_Sort.next.next.next.next.next.next.next.next.next = new MyList(2);

9-->8-->8-->7-->5-->4-->6-->3-->1-->2-->TAIL
4

2 に答える 2

0

次のロジックを使用して、スキップしたくない最初の要素にトラバースできます

List tmp = L;
while (tmp != null && doSkip(tmp.data)) {
  tmp = tmp.next;
}

次に、削除したくない最初の要素に移動します。

List tmp2 = tmp;
while (tmp2 != null && doDelete(tmp2.data)) {
  tmp2 = tmp2.next;
}

次に、次の fromを最初の no-delete 要素にリンクして、tmpとの間の要素を削除します。tmp2tmp

tmp.next = tmp2;

ここでdoSkip()anddoDelete()は、それぞれ要素をスキップするか削除するかを評価します。ロジックにシーケンスの評価が含まれる場合、何らかの状態を保持する必要がある場合があります。

このアプローチは、反復トラバーサル (再帰的ではない) を使用します。これは、問題により適していると思います。

于 2012-04-30T19:12:43.667 に答える
0

わお！！それは確かに a をトラバースする方法ではありませんLinkList。ノードがある場合、時間10000を書くことはできません.next 9999:-)

よくわからない場合は、できるだけ再帰を使用しないようにしてください。ループの方が使いやすいです。ループを使用します。

while(current.next != null)
{
    //do your stuff
    current = current.next;
}

そして、私の記憶が正しければ、あなたは以前、どのように並べ替えるかについて尋ねました0s and 1s. そこでやったのと同じことをします。ポインタを使用してノードを追跡します。削除したいノードの直前にあるノードにトラバースするだけです (currentポインターを使用)。次に、参照用のポインターをそこに置きます。次に、削除するノードまで (ポインターを使用して) トラバースを続けpresentます。次に、削除するノードの次のノードを正確に指すように、前にもう 1 ホップ移動します。今行う：

current.next = present;

ヴォラ!! 終わった

于 2012-04-30T19:12:23.177 に答える