r：単方向リストの全反転
まず、このリンクリストを見てみましょう
例えば、次のようなリンクリストがあるとします：
head
↓
1 → 2 → 3 → 4 → null
図中の各ノードの位置はそのままに、ノード間の参照関係を逆にする：
null ← 1 ← 2 ← 3 ← 4
↑
head
どうやら 1 これは先頭ノードであり、前のノードは存在しません。反転すると、1 そうすると末端ノードとなり、その next リンク先を指定する必要があります null、新しいルートノードは 4。
新しいルートノードから 4 沿って next さあ、アクセス順序は次の通りです。 4 → 3 → 2 → 1 → null。変化するのはポインタと走査順序であり、各ノード内の値は入れ替わっていない。
1つのノードには何が含まれているのでしょうか？
まず、「ノード」という概念について補足しておきます。ここでの各ノードには、2つのフィールドがあります：
.value：このノードに保存されている値。.next：次のノードへの参照。
なお、以下で「現在のノード」と言う場合、そのノード全体を指し、単にその中に含まれる値だけを指すわけではありません。
私たちは c 現在のノード、つまり「current」を表します。c.value その値は、c.next それが指し示す次のノードです。
逆順のリンクリストを処理する際、value そのままで結構です。変更するのはノード間の参照です。
3つの変数を用意する
始める前に、3つの変数を用意します。それぞれ、前のノード、現在のノード、および現在のノードの本来次のノードを格納します：
let p = null; // previous：前一个节点
let c = head; // current：当前节点
p 最初は等しい null、なぜなら、私たちはルートノードから開始するため、その前にはノードが存在しないからです。
c 最初は等しい head、つまり、連結リストの先頭ノードです。
もう一つ n、は「next」を表す。これは、各ラウンドで現在のノードを処理する際に保存される：
let n = c.next;
なぜわざわざ次のノードを格納するための変数を用意する必要があるのでしょうか？
参照先を変更する前に、その先のノードを保存しておく
このリンクリストのグループに戻ってみましょう：
1 → 2 → 3 → 4 → null
あるノードの next フィールドには一度に1つの参照しか保存できません。ノードは複数存在しても構いません。 next 同じノードを指しているが、1つ next 2つのノードを同時に指すことはできません。
だからこそ、私たちは変わらなければならない 1 が指している先を、元の指し示していた先に戻す必要があります 2 の引用を置き換える。
しかし、直接変更すると、その先の 2 → 3 → 4 どうすればいい？もうここを通れなくなってしまった 1.next 見つけたよ。
そこで、まずは別の場所に保存しておきましょう：
let n = c.next;
これをしっかりと保管したら、操作を開始できます。 c.next ：
c.next = p;
第1ラウンドでは、c ノードです 1，p はい null。したがって、この手順を終えると、次のようになります：
c n
↓ ↓
1 → null 2 → 3 → 4 → null
ほら、c.value 私たちは動かなかった。なぜなら、それは変わらないからだ。c.next 修正も完了しました。これでこのノードの処理は終わりました。とても手早く済みました。
さて、次は次のノードの処理の準備に取り掛かる番だ。
変数を後ろに移動する
ここで、先ほど定義した変数を移動しますが、その順序は次のとおりです：
p = c;
c = n;
なぜこのように動かすのですか？
現在のノードはすでに処理が完了しているため、次の処理サイクルまで待ちます。 2 このとき、それが参照する「前のノード」とは、先ほど処理が完了したノードのことです。 1。
そこで、まずは…… p = c、現在のノードを次のループの前のノードとして保存する。
では、現在のノードを誰に変更すればよいのでしょうか？それは、先ほどあらかじめ保存しておいた「次のノード」です。 n、ですから c = n。
ここではまず保存する必要があります p = c、それから移動する c。もしまず c 次のように変更する n、それから書く p = c，p 保存されるのは、先ほど処理したノードではありません。
第1ラウンド終了後：
p c
↓ ↓
1 → null 2 → 3 → 4 → null
これで次のノードへと進み、次のループが始まります。
次のノードも同様です
今 c 重要な局面を迎えた 2。
まず、元のノードの次のノード、つまりノードを保存します。 3：
let n = c.next;
次に、現在のノードの参照先を変更します：
c.next = p;
そのとき p ノードへのポインタ 1、したがって、このステップでは 2 指向 1。
変数を再度移動：
p = c;
c = n;
第2ラウンドが終了すると、次のようになった：
p c
↓ ↓
2 → 1 → null 3 → 4 → null
その後も同様で、引き続き処理を進めます：
第三轮结束：
p c
↓ ↓
3 → 2 → 1 → null 4 → null
第四轮结束：
p c
↓ ↓
4 → 3 → 2 → 1 → null null
したがって、私たちのループ条件は次のようになります：つまり、 c まだ等しくない null、ずっと続けていく。
など c ～になる null、これはすべてのノードの処理が完了したことを示しています。この時点で p これは、反転後のリンクリストの先頭ノードを指しているため、最終的に返されるのは p。
完全なコード
JavaScript で書くと、こうなります。渡されてきたものが head これはルートノードであり、各ノードには value と next フィールド、リンクリストの末尾の next はい null：
function reverseList(head) {
let p = null;
let c = head;
while (c !== null) {
let n = c.next; // 先保存原来的下一个节点
c.next = p; // 把当前节点的指向反过来
p = c; // 当前节点成为下一轮的前一个节点
c = n; // 继续处理原来的下一个节点
}
return p;
}
各ラウンドは、実は4つのステップで構成されています：
- 次のノードを保存します。
- 現在のノードの参照先を変更する。
- ～にさせる
p処理が完了したばかりのノードを指します。 - ～にさせる
c次の処理対象ノードに移動します。
このプロセス全体を通じて、ノード内の値は交換されず、変更されたのはすべて next。各ノードは1回だけ処理されるため、時間計算量は O(n)；これらの変数だけを使用した場合、追加の空間複雑度は O(1)。
もし渡されてきたものが空のリンクリストである場合、c 最初から null、ループは実行されず、そのまま戻る null。ノードが1つしかない場合、1ラウンド処理した後も、返されるのはそのノードのままです。
