解答と解説: Reverse a Singly Linked List

「問題演習: Reverse a Singly Linked List」の解答編です。この問題は単方向リストを逆順に並び替えるという一見すると単純に見える問題ですが、空間計算量を O(1) で処理しなくてはならない点が難易度を上げています。

念のため空間計算量 O(1) という制約について確認しておきましょう。空間計算量 O(1) を換言すると、メモリの使用量は入力に依存することなく、一定でなくてはならないということです。参考までに言及しておくと、リストを複製することはリストの長さを n としたときメモリの使用量は n に依存するので O(n) になってしまいます。

以上を確認した上で、解答を見てみましょう。

解答例

Javaでの解答例です。

解答１）

解答２）

解説

解答１の解説

この問題の解法は複数存在するのですが、解答１の考え方が一番シンプルだと思います。この解法では、引数として与えられたリストの先頭ノード head から順に後方に向かって走査する際に、各ノードをこれまでに走査したノードの中での先頭のノードにしてしまおうという考え方です。下記に各操作における head と newHead の値について示しました。

1. 初期状態
   • head は単方向リスト「1 -> 2 -> 3 -> 4 -> 5 -> null」の 1 を指す。
   • newHead は null 。
2. ノード 1 が head から newHead に移る。つまり head は 1 の後ろのノードである 2 を指し、newHead が新たなリストの先頭ノードとして 1 を持つ。
   • head は 単方向リスト「2 -> 3 -> 4 -> 5 -> null」の 2 を指す。
   • newHead は 単方向リスト「1 -> null」の 1 を指す。
3. ノード 2 に対して同様の操作を行う。
   • head は 単方向リスト「3 -> 4 -> 5 -> null」の 3 を指す。
   • newHead は 単方向リスト「2 -> 1 -> null」の 2 を指す。
4. ... 最後）すべてのノードの操作を終えたので、head が null を指している。newHead は逆順になったリストの先頭ノードとして 5 を指す。
   • head は null 。
   • newHead は 単方向リスト「5 -> 4 -> 3 -> 2 -> 1 -> null」の 5 を指す。

解答２の解説

解答１のような解法が思いつかなくても、少し複雑ですが解答２の方法で解ければ問題ないです。解答２の手法としては、リストを後方に走査する際に引数として与えられたリストの先頭ノード head を変化させず、末尾に到達するまで次のノードをリストの先頭に移動させます。

1. 初期状態
   • head は単方向リスト「1 -> 2 -> 3 -> 4 -> 5 -> null」の 1 を指す。
   • newHead も単方向リスト「1 -> 2 -> 3 -> 4 -> 5 -> null」の 1 を指す。
2. ノード 1 が head から newHead に移る。つまり head は 1 の後ろのノードである 2 を指し、newHead が新たなリストの先頭ノードとして 1 を持つ。
   • head は単方向リスト「2 -> 1 -> 3 -> 4 -> 5 -> null」の 1 を指す。
   • newHead 単方向リスト「2 -> 1 -> 3 -> 4 -> 5 -> null」の 2 を指す。
3. ノード 2 に対して同様の操作を行う。
   • head は単方向リスト「3 -> 2 -> 1 -> 4 -> 5 -> null」の 1 を指す。
   • newHead 単方向リスト「3 -> 2 -> 1 -> 4 -> 5 -> null」の 3 を指す。
4. ... 最後）すべてのノードの操作を終えたので、head が null を指している。newHead は逆順になったリストの先頭ノードとして 5 を指す。
   • head は単方向リスト「5 -> 4 -> 3 -> 2 -> 1 -> null」の 1 を指す。
   • newHead 単方向リスト「5 -> 4 -> 3 -> 2 -> 1 -> null」の 5 を指す。

その他の解法

主な解法は上記の 2 つになりますが、再帰を使って同様の解法を実装することができます。これは各自考えてみてください。

まとめ

この問題はプログラムの行数は長くはないですが、解法が思いついてもプログラムを作成する際に混乱しやすい問題です。良い解法が思いついたとしても、プログラム作成中に詳細を忘れてしまうこともあるかもしれません。また、面接ではプログラムを作成した後に、そのプログラムがどのように動くかを説明させられます。上記の解説で示したような説明をする必要があるのですが、かなり具体的なイメージがないと自信を持って説明することがなかなかできません。

対策としては、プログラムを書き始める前に紙やホワイトボードに図を書くことをオススメします。その図の通りにプログラムを記述し、手順の説明をしてしまえば良いのです。一度得られた具体的なイメージを損なうことがないように、工夫しましょう。
---
シリコンバレーでエンジニアとして就職するには、アルゴリズムやプログラミング、システムデザインの問題が出題される面接を突破する必要があります。本サイトでは、シリコンバレーでエンジニアとして働き、面接官としての経験も豊富な筆者が、面接への対策に関する情報を配信しています。