リンクリストの反転
ブラウザの履歴は、今いるページから 1 つ前へ、また 1 つ前へとたどれるようにつないであります。これを逆側からたどれる形に作り替えるのが反転です。札の向きを 1 本ずつ裏返していきます。
裏返した瞬間、次がどこか分からなくなる
先頭から順に、next を 1 つ前のノードへ向け直していけばよさそうに見えます。ところが素直に書くと、2 個目で止まります。
Python
prev = None
cur = head
while cur is not None:
cur.next = prev # ここで元の行き先が消える
prev = cur
cur = cur.next # もう prev を指しているcur.next を書き換えた時点で、元々の行き先を書いた札は上書きされています。次の行で cur.next を読んでも、返ってくるのは今しがた自分で書いた prev です。1 歩も先へ進めないまま、来た道を戻ることになります。
上書きする前に、行き先を手に持っておく
必要なのは 3 つ目の変数です。裏返す前に、元の行き先をそこへ退避します。
Python
prev = None
cur = head
while cur is not None:
nxt = cur.next # 逃がす
cur.next = prev # 裏返す
prev = cur # 2 つそろって 1 歩進む
cur = nxt逃がす、裏返す、進む。この順番が命です。prev cur nxt の 3 つを持つ理由は、裏返す一手で片方の情報が必ず消えるからにほかなりません。消える前に手に持っておく、それだけのために 3 つ目がいます。
1 -> 2 -> 3 の 1 周目を追ってみます。nxt が 2 を受け取り、1 の札が空を向き、prev が 1、cur が 2 へ移ります。2 周目で 2 の札が 1 を向きます。鎖が一度にひっくり返るのではなく、前から 1 本ずつ向きが変わっていく様子が見えるはずです。
JavaScript でも変わりません。
JavaScript
let prev = null;
let cur = head;
while (cur !== null) {
const nxt = cur.next;
cur.next = prev;
prev = cur;
cur = nxt;
}なお、prev の初期値が空なのも意味があります。元の先頭は反転後の末尾になるので、その next は空でなければなりません。最初の 1 回で cur.next = None が入り、末尾の印がそこに置かれます。
返すのは cur ではなく prev
ループを抜けたとき cur は空です。末尾の 1 つ先まで来ているからです。新しい先頭は、最後に裏返したノード、つまり prev の側に残っています。ここを取り違えると、戻り値が空になって「なぜか何も返ってこない」という状態になります。
裏返し終わるまで、元の並びをたどる手段は 1 つも残りません。だから途中で状態を確かめたいときは、反転の前に値を控えておく必要があります。
今回の課題は配列で同じことをします。札が無いぶん変数 3 つは要りませんが、順序を 1 か所ずつ入れ替えていく感覚は変わりません。手を動かす前に、3 要素の列を紙に書いて、どこから何を動かすと壊れないかを追ってみてください。
要件
- 連結リストは配列 arr で表現する
- 戻り値は反転した新しい配列
- 元の配列を破壊的に変更しても良いが、戻り値が反転していること
入出力例
reverseList([1,2,3]) → [3,2,1]
reverseList([10]) → [10]
reverseList([1,2,3,4,5]) → [5,4,3,2,1]
reverseList([7,8]) → [8,7]
reverseList([1,1,2,2]) → [2,2,1,1]ヒント
