【ITニュース解説】LeetCode 206: Reverse Linked List - (Easy)

システムエンジニアを目指す上で、データ構造とアルゴリズムの理解は不可欠だ。今回は、最も基本的なデータ構造の一つである「連結リスト」とその操作の中から、「リストの反転」という課題について解説する。プログラミング学習プラットフォームなどでよく出題されるこの問題は、連結リストのポインタ操作を理解する上で非常に良い演習となる。

まず、連結リストとは何かを理解する必要がある。一般的なデータの集合である配列は、メモリ上でデータが連続して並んでおり、インデックス（番号）を使って直接アクセスできる。しかし、連結リストは異なる。連結リストは「ノード」と呼ばれる要素が鎖のようにつながった構造をしている。各ノードは、自分が持っているデータと、次のノードがどこにあるかを示す「ポインタ」（あるいは参照）の二つの情報を持っている。最後のノードは次のノードが存在しないため、ポインタは「null」（何も指していない状態）となる。そして、リスト全体の先頭を示すのが「ヘッド」（head）と呼ばれるポインタだ。このヘッドからたどっていくことで、リスト内のすべてのノードにアクセスできる。

今回の課題は「単方向連結リストが与えられたとき、そのリストを反転させて、反転されたリストを返す」というものだ。例えば、「1 -> 2 -> 3 -> null」というリストがあれば、それを「3 -> 2 -> 1 -> null」という形に変える必要がある。これはつまり、各ノードが指す「次のノード」の方向を逆にする操作を意味する。

このリストの反転を実現するアプローチは、非常に巧妙なポインタ操作を用いる。具体的には、「prev」（前のノード）と「curr」（現在のノード）という二つのポインタを使ってリストを順に進んでいく。

処理の開始時には、prevポインタはまだどのノードも指していない状態なので null に初期化する。currポインタは、処理を開始するリストの先頭、つまりheadノードを指すように初期化する。

リストの先頭からcurrポインタがnullになるまで、つまりリストの最後まで、以下の処理を繰り返す。

1. 次のノードを一時的に保存する: 現在のノードcurrのポインタcurr.nextは、本来の次のノードを指している。しかし、この後curr.nextの指す先を変更するため、元の次のノードを見失わないように、先に一時変数nextNodeに保存しておく必要がある。このnextNodeが、次のループでcurrが移動すべき場所となる。

2. 現在のノードのポインタを反転させる: curr.next = prev; という操作が、まさにリストを反転させる核心だ。現在のノードcurrが、もともとcurrの前にあったノード、つまりprevが指しているノードを指すようにする。最初のノードを処理する際、prevはnullなので、最初のノードはnullを指すことになる。これは、新しい反転されたリストにおいて、最初のノードが「末尾」になることを意味する。

3. prevポインタを進める: 現在のノードcurrのポインタを反転させたら、prevポインタをcurrが指していた位置に進める。次のループで処理されるノードにとって、現在のcurrが「前のノード」となるためだ。つまり、prev = curr; とすることで、prevが現在処理し終えたノードを指すようになる。

4. currポインタを進める: currポインタは、リストの次のノードに進む必要がある。ステップ1で保存しておいたnextNodeをcurrに代入することで、リストを一つ先に進める。つまり、curr = nextNode;とする。

これらのステップをcurrがnullになるまで、つまりリストのすべてのノードを処理し終えるまで繰り返す。currがnullになったとき、それはリストの末尾までたどり着いたことを意味する。この時点で、prevは元のリストの末尾のノードを指している。そして、その元の末尾のノードは、新しい反転されたリストの先頭になっているため、prevが新しいヘッドとなる。

具体的なコードは以下のようになる。

ListNode ReverseList(ListNode head)という関数がheadという名前のListNode（リストの先頭ノード）を受け取る。

まず、prevというListNode型の変数をnullで初期化する。これは、最初のノードを処理する際にその「前」に何も存在しないことを示すためだ。次に、currというListNode型の変数を、入力として受け取ったheadで初期化する。これがリストの走査を開始する初期状態だ。

while (curr != null)というループは、currがnullになるまで、すなわちリストのすべてのノードを処理し終えるまで続く。

ループの内部では、ListNode nextNode = curr.next;によって、現在のノードcurrが指す次のノードをnextNodeに一時的に保存する。これは、現在のノードのポインタを変更する前に、リストの残りの部分への参照を失わないようにするため、非常に重要な処理だ。

次に、curr.next = prev;によって、現在のノードcurrのnextポインタを、一つ前のノードであるprevが指すように変更する。これが「反転」の肝となる操作だ。

そして、prev = curr;によって、prevポインタを現在のノードcurrの位置に進める。次のイテレーションでは、現在処理したcurrが前のノードとなるためだ。

最後に、curr = nextNode;によって、currポインタを、先ほどnextNodeに保存しておいた、元のリストでの次のノードへと進める。これにより、リストを一つずつ処理していくことができる。

このループが終了すると、currはnullになっており、すべてのノードが反転されている。prevは最後に処理されたノード、つまり元のリストの末尾ノードを指しているが、このノードは新しい反転されたリストの先頭ノードとなるため、return prev;によってその新しいヘッドが返される。

このアルゴリズムは、連結リストの各ノードを一度だけ走査するため、リストの長さNに対して線形時間計算量O(N)で動作する。また、追加のデータ構造をほとんど使わず、定数個のポインタ変数のみを使用するため、空間計算量O(1)という効率的な解決策となっている。システムエンジニアとして、このような効率的なデータ構造の操作方法を理解することは、パフォーマンスの良いソフトウェアを開発するために非常に重要だ。