java - リンクされたリストを元に戻す方法を理解していますか?

Question

リンクされたリストを元に戻すための次のコードがあります。

node old = head;
head = null;

while (old!=null) {
   node temp = old.link;
   old.link = head;
   head = old;
   old = temp;
}

ボックス ダイアグラムを描画してリストを逆にする方法を確認しようとしていますが、まだ理解できないため、このコードの各行を説明してください。

Answer 1

headリスト (1、2、3、4) の先頭へのポインターであると仮定します。

+-----+ link +-----+ link +-----+ link +-----+ link
|  1  | ---> |  2  | ---> |  3  | ---> |  4  | ---> null
+-----+      +-----+      +-----+      +-----+
 ^ head

古いノード = 頭;
頭 = null;

+-----+ link +-----+ link +-----+ link +-----+ link
|  1  | ---> |  2  | ---> |  3  | ---> |  4  | --->  null
+-----+      +-----+      +-----+      +-----+
 ^ old

                                                     null

                                                      ^ head

(whileループの最初の反復...)
node temp = old.link;

+-----+ link +-----+ link +-----+ link +-----+ link
|  1  | ---> |  2  | ---> |  3  | ---> |  4  | --->  null
+-----+      +-----+      +-----+      +-----+
 ^ old        ^ temp

                                                     null

                                                     ^ head

old.link = 頭;

+-----+ link +-----+ link +-----+ link +-----+ link
|  1  | -+   |  2  | ---> |  3  | ---> |  4  | --->  null
+-----+  |   +-----+      +-----+      +-----+
 ^ old   |    ^ temp
         |                            
         +---------------------------------------->  null

                                                     ^ head

頭=古い;

+-----+ link +-----+ link +-----+ link +-----+ link
|  1  | -+   |  2  | ---> |  3  | ---> |  4  | --->  null
+-----+  |   +-----+      +-----+      +-----+
 ^ old   |    ^ temp
 ^ head  |                             
         +---------------------------------------->  null

古い = 温度;

             +-----+ link +-----+ link +-----+ link
             |  2  | ---> |  3  | ---> |  4  | --->  null
             +-----+      +-----+      +-----+
              ^ old
              ^ temp                   +-----+
                                       |  1  | --->  null
                                       +-----+
                                        ^ head

(2 回目の反復...)
node temp = old.link;

             +-----+ link +-----+ link +-----+ link
             |  2  | ---> |  3  | ---> |  4  | --->  null
             +-----+      +-----+      +-----+
              ^ old        ^ temp
                                       +-----+ link
                                       |  1  | --->  null
                                       +-----+
                                        ^ head

old.link = 頭;

             +-----+ link +-----+ link +-----+ link
             |  2  | -+   |  3  | ---> |  4  | --->  null
             +-----+  |   +-----+      +-----+
              ^ old   |    ^ temp
                      |                +-----+ link
                      +--------------> |  1  | --->  null
                                       +-----+
                                        ^ head

頭=古い;

             +-----+ link +-----+ link +-----+ link
             |  2  | -+   |  3  | ---> |  4  | --->  null
             +-----+  |   +-----+      +-----+
              ^ old   |    ^ temp
              ^ head  |                +-----+ link
                      +--------------> |  1  | --->  null
                                       +-----+

古い = 温度;

                          +-----+ link +-----+ link
                          |  3  | ---> |  4  | --->  null
                          +-----+      +-----+
                           ^ old
                           ^ temp

                          +-----+ link +-----+ link
                          |  2  | ---> |  1  | --->  null
                          +-----+      +-----+
                           ^ head

old最後に null を指すまで (つまり、元のリストが空になるまで)繰り返します。

Answer 2

コードの各行で何が起こるかを描くのに役立ちます

これに従っていただければ幸いです。コードの各行にループ 1 ～ 3 までの番号を付け、ループ内では次のように A、B、C、D にします。

1. Node old = head;
2. head = null;

3. while (old!=null) {
A.    Node temp = old.link;
B.    old.link = head;
C.    head = old;
D.    old = temp;
   }

編集：下の図を少しカットしてください。Head は、新しい最初のノード (図の最後のノード) を指す必要があります。Temp と Old は両方とも Null である必要があります。以前は最初だった Node は、現在は最後の Node であるため、Null を指しています。したがって、正常に反転されます。