1 
public void reverse(Node curr) {
      if (isEmpty()) {
          return;
      }

      if (curr.next == null) {
          head = curr;
          return;
      }

      reverse(curr.next);
      curr.next.next = curr;
      curr.next = null;

  }

私は再帰を学ぼうとしています..私の最も弱い点であり、これがどのように機能するかを理解していません.2番目のノードで始まることがわかります..次に、現在の次のノードになり、リンクがnullになります...私はそれを理解していません。初心者の質問で申し訳ありません。私が理解していることにさらに追加します..しかし、残念ながらそれは本当にそれについてです..

4

5 に答える 5

6

私も理解できないので、サンプル コードを完全に無視します。この問題 IMO について考える最も簡単な方法ではありません。これについて一緒に概念的に考えてみましょう。

  1. 誰かが空のリストを渡した場合はどうなりますか? 空のリストを返す必要があります
  2. 誰かが 1 つの要素のリストを返すとどうなりますか? 渡されたものを返す必要があります
  3. 誰かが 2 つ以上のリストを返すとどうなりますか? リストの最後の要素を取り、それを前に置き、次に呼び出しますlast + reverse(listWithLastRemoved)

2 つのリストでこれを試してみましょう。その[a, b]中にあります。それを渡すと、ステップ #3 が実行されます。その結果、次のようになります。

b + reverse([a])

左側はしばらく無視してください。 ステップ＃2に一致するため、reverse([a])返されます。[a]評価できるのは

b + [a]

そして、それは次のように評価できます

[b, a]

これは疑似コードであることに注意してください。+リストの先頭に要素を追加することを暗示するために 使用しています。

もう一度試してみましょう。ただし、今回は 3 つの要素を使用し[a b c]ます。

[a b c] #apply step #3
c + reverse([a b])  #apply step #3
c + b + reverse([a]) #apply step #2
c + b + [a] #add b to [a]
c + [b a] #add c to [b a]
[c b a]

あなたが指摘したように、最後の要素を取得するには、リストを「反復」して最後の要素を見つける必要があります。ループを使用する必要があるようにfor思えますが (これは再帰的ではありません)、最後の取得も再帰的に行うことができます。実際、そのアルゴリズムはより単純でreverseあり、最初から練習するのに適していたでしょう。の手順を説明しますgetLast。

  1. 誰かが空のリストを渡した場合はどうなりますか? nullを返す必要があります
  2. 誰かが 1 つの要素のリストを返すとどうなりますか? 最初の要素を返す必要があります
  3. 誰かが 2 つ以上のリストを返すとどうなりますか? リストの最初の要素を削除してから、残りを に渡しgetLastます。

で試してみましょう[a b c]：

[a b c] #apply step #3
getLast([b c]) #apply step #3
getLast([c]) #apply step #2
c

最後のステップは、リストではなく要素を返すことに注意してください。

于 2013-06-17T23:20:41.333 に答える
2

ここに解決策を説明するための擬似コードがあります

// method takes a list and returns the list reversed
// it will corrupt the existing list so do not use it
// after calling this method.
// works by finding the last node and building a list from there
public Node reverseList(Node list){
    // have we found the last node yet?
    if (list.isLast()){
        return list;
    } else {
      // reverse the list after the current node
      Node newList = reverseList(list.next());
      // add current node to end of new list
      addToLast(list,node);
      // return new list
      return newList;
    }

}

public void addToLast(Node list, Node newNode){
    // add newNode to the end of list.
}
于 2013-06-17T23:22:40.940 に答える
1

これも最初は少し奇妙でしたが、実際には非常に理にかなっています。

public void reverse(Node curr) 
{
      if (isEmpty()) //obvious 
      {
          return;
      }

      if (curr.next == null) //once we get to the last element, assign it to head
      {
          head = curr;
          return;
      }

      //explained below
      reverse(curr.next); 
      curr.next.next = curr;
      curr.next = null;  
  }

最後から 2 番目の要素にいる場合を考慮して、最後の 3 行を分析してみましょう。

を呼び出しますreverse(curr.next)。その呼び出しcurr.next == nullではhead = curr、この場合currは最後の要素であり、戻ります。

ここで、 atcurr.next.next = currはcurr元のリストの最後から 2 番目の要素です。

curr.next元の最後curr.next.next = currの要素であり、元のリストの最後から 2 番目の要素を、元のリストの最後の要素の次の要素に割り当てます。

curr.next = null次に、next要素 (3 番目の要素) を list に作成しnullます。繰り返し、したがってリストを逆方向に拡張します (最後の要素は になりますnull)。

これでも意味が分からない場合は、ペン、本、あなたが持っているものを 3 つつかんでみcurrてcurr.nextください。呼び出しをたどり、実際のオブジェクトを使用して物事を追跡すると役立つ場合があります。これで問題が解決することを願っています。幸運を。curr.next.nextnull

于 2013-06-17T23:43:24.750 に答える
1

これを考える 1 つの方法は、小さな例を使用することです。まず、2 つのエッジ ケース:

  1. リストが空の場合は、すでに逆になっています (簡単に)
  2. currが単一のノードである場合、それはそれ自身の反転です (繰り返しますが、自明です) 。したがって、現在のリストの先頭を に設定しcurrます。

これらのどちらも当てはまらないと仮定すると、最後のコード ブロックがどのように機能するかを理解するのが難しいことになります。おそらく、プロセス全体は を呼び出すことによって開始されreverse(head)ます。2 要素リストで何が起こるか見てみましょう。

head = curr(0)
  |
  V
+---+  +---+
| 0 |->| 1 |->null
+---+  +---+

再帰呼び出しごとに新しい が作成されるため、適用される再帰のレベルを示すインデックスでcurr注釈を付けました。currへの呼び出しがありreverse(curr.next)ます。その呼び出し中、メソッドの開始時の画像は次のようになります。

head   curr(1)
  |      |
  V      V
+---+  +---+
| 0 |->| 1 |->null
+---+  +---+

これは 2 番目のエッジ ケースを満たすため、メソッドは図を次のように変更します。

       head = curr(1)
         |
         V
+---+  +---+
| 0 |->| 1 |->null
+---+  +---+

curr(要素が 1 つのリストでしたが、その要素は ではなかったことに注意してくださいhead。これが、すべてが機能する理由の鍵です!) メソッドが戻り、最初の呼び出しに戻ります。写真は次のようになります。

curr(0) head
  |      |
  V      V
+---+  +---+
| 0 |->| 1 |->null
+---+  +---+

コードの 2 行目 (3 番目のブロック内) はcurr.next.next = curr;. これにより、画像が次のように変更されます。

curr(0) head
  |      |
  V      V
+---+  +---+
| 0 |->| 1 |--\
+---+  +---+  |
  ^           |
  |           |
  \-----------/

最後に、次のように設定しますcurr.next = null;。

curr(0)       head
  |             |
  V             V
+---+         +---+
| 0 |->null   | 1 |--\
+---+         +---+  |
  ^                  |
  |                  |
  \------------------/

それを少し見つめてみると、実際にはリストが逆になっていることがわかります。

同じ手法を使用して、これが長いリストを逆にする方法を確認できます。これについて考える最も簡単な方法は、呼び出すreverse(curr.next)とリストの末尾が逆になり、次の 2 行がcurrリストの末尾に追加されるということです。

于 2013-06-17T23:34:06.357 に答える
1

あなたがウォークスルーを求めたので：

public void reverse(Node curr) {
      if (isEmpty()) {
          return;
      }

リストの最後に達した場合は、何もする必要はありません。

      if (curr.next == null) {
          head = curr;
          return;
      }

引数がリストの最後のノード ( curr.next == null) でheadある場合、元の最後のノードが反転リストの最初のノードであるため、そのノードに設定します。

      reverse(curr.next);

それ以外の場合は、リストの末尾を逆にします (現在のノードの後のすべて)。結果のリストの最後のノードは です。これはcurr.next、ここで逆にしたリストの最初のノードだったからです。

      curr.next.next = curr;

現在のノードを反転リストの最後に追加します。便利なことに、その最後のノード、つまり への参照がまだありますcurr.next。

      curr.next = null;

反転リストの最後のノードであるためnext、現在のノードのフィールドを に設定します。null

}
于 2013-06-17T23:34:45.923 に答える