リンクリストを再帰的に逆転する

Question

問題は、ノードの順序が逆になるように、単一リンクリストLを逆転させるための再帰アルゴリズムを書く必要があることです。 これは少し抽象的ですが、私はコードや何も必要ないし、問題がアルゴリズムを要求して以来、私は固執しています。 私は始めるべきかどうか分かりませんが、私はリンクリストに関していくつかの簡単なことがあったことを意味します。正面に追加して削除するようなものですが、逆転（特に再帰的）は壁のようです。あなたが特定のコードを提供する必要はありませんので

Answer 1

、でしょう私もあなたの擬似コードを与えた場合、私はあなたの宿題をやっていると思いますので、私はちょうどあなたにいくつかのヒント;-)

一般的なアプローチをあげます

1. （与えられたリストが空の場合、空のリストを返し、）基本ケースをカバーし
2. 再帰を行うとテールに
3. を反転させる反転尾に頭を追加すること。 A-> B-> NULL：

reverse(1 -> 2 -> 3) 
= reverse(2 -> 3) -> 1 
= reverse(3) -> 2 -> 1 
= reverse() -> 3 -> 2 -> 1 
= emptyList -> 3 -> 2 -> 1 
= 3 -> 2 -> 1 

Answer 2

は、2つのノードリストの単純なケースを考えてみましょうようにそれが行くだろう1 -> 2 -> 3を逆にします。そのリストを逆にしてB-> A-> NULLになるようにするにはどうしますか？

まだ入手できない場合は、レゴのスタックがリンクリストであるとします。レゴを切断して再接続して、実際の生活の中で並べ替えを実行し、実行する各ステップをメモします。

Answer 3

私たちはLで最初n ≤ L.size()ノードを反転させ、そして我々が行われL.size() ≤ 1場合は、単にL (end = null if n = L.size())のn番目のノードの後に​​ノードへのポインタの終わりを返すメソッドreverse(L, n)を定義してみましょう、そう私たちは、Lは、少なくとも2を持っていると仮定しましょうノード。 n = 1を返した場合はL.first().next()を返します。そうでない場合は、reverse(L, n - 1)を再帰的に呼び出し、Lのn番目のノードに返されたポインタをendとします。の場合はn < L.size()に、そうでない場合はnullに設定します。次に、Lの前にendで指されたノードを挿入し、retを返します。

FYI、合計実行時間はO（n）です。