1

LinkedList以下の逆コードがどのように機能するかを理解しようとしています...

public void reverse(Node<T> h) {
  Node<T> d = new Node<T>();
  Node<T> t;
  while (h.next != null) {
     t = h.next; //temp nodes points to h.next (1st item in list)
     h.next = t.next; //h.next bypasses first node in list.
     t.next = d.next; //t.next points to d.next.. where is d.next pointing to?
     d.next = t; //d.next now points to t.
  }
   h.next = d.next;
  }

このプロセスはどのように機能しますか？

ダイアグラムは素晴らしいでしょう。あるリストのノードがポップオフされて新しいリストにプッシュされたようです。この場合、hリストが逆になっていることを示していますか？

4

1 に答える 1

1

私自身への更新と、チャレンジの編集：

アルゴリズムは機能しますが、紛らわしい方法で記述されており、最初のノードが含まれていません(副作用のためにのみ使用されます)。これは、それ自体が疑わしい設計です。

役に立たないものを避けてd.nextスコープをtより良くするように書き直すと、従うのが簡単になります（そして私にとっては可能です）：

public void reverse(Node<T> h) { // draw H under first node
  Node<T> d = null
  while (h.next != null) {
     Node<T> t = h.next;  // draw T under box at end of H arrow (remove any previous T)
     h.next = t.next;     // change arrow from H to end where arrow from box above T ends (no arrow for last element)
     t.next = d;          // draw arrow from box above T to box D is under (no arrow for first element)
     d = t;               // draw D under box (remove any previous D)
   }
   h.next = d;            // draw arrow from H to box D is under
}

ボックスに！

( Reverse a Linked-Listのコードを見ることをお勧めします。これは同じ概念ですが、従うのが簡単で、この実装の偽のヘッド ノードがありません。)

「箱を描くだけ」と言ったことは知っています。それで、あなたのコメントをさらにいくつか聞いた後、私は箱を描きました。(私は大学に戻ったふりをしました ;-)

ただし、動作させることもできません。サークルもやってみた。

投稿されたコードは機能する実装ではないと思われます（これは、他の人が私が間違っていることを証明するための未解決の課題です。少なくとも、この質問を開いたままにしておく可能性があります;-)

何度か試行した後、長さが 2、3、または 4 要素のリストを逆にするためにそれを使用することはできませんでした (ただし、Reverse a Linked-Listに示されている [はるかに直感的な] コードを正常に使用することはできました)。

「ルート」ノードのh.next代わりに使用することに欠陥があると思います。hおそらく、作者はvoidダミーノードと副作用を伴うリターンを説明していますか? しかし、その場合、行h.next = t.nextはまだアルゴリズムを壊しているようです.

于 2012-06-25T02:34:49.027 に答える