一定のスペースと私は面接の質問を聞いた

Question

線形時間で、後方重リンクリストを印刷します：「一定の空間と線形時間で、後方 を単独リンクリストの印刷」

を

私の解決策は、リンクされたリストを所定の位置に戻し、そのように印刷することでした。非破壊的なソリューションがありますか？

Answer 1

あなたは元の順序が復元されているので、それはもはや、破壊できなくなります印刷した後、再びそれを逆にした場合。

Answer 2

あなたが書きたいものを参照して、リンクされたリストチェーンを再帰呼び出しすることができます。各ノードは、自身を印刷する前に参照を渡しながら、子ノードの印刷機能を使用します。

リスト内の各ノードが通過して最後のノードが書き込みに成功しなくなり、書き込みにまっすぐに進むまで、チェーンをバックアップする各ノードは最後まで最後まで書き込みます。

編集

この実際にあるため、スタック上の線形空間の仕様に適合していません。もしあなたが関数や文字列の前に書き込むメソッドを歩くために何かを持っていれば、基本ロジックはまだ動くことができます。

Answer 3

ちょうど反復して途中で印刷しますが、モニターは上下逆さまになります。

˙uoıʇɐɯɹoɟsuɐɹʇʇxǝʇǝlʇʇılɐɥʇıʍʇɥƃıɹʇsoɯlɐʞooluɐɔʇI

Answer 4

これは通常とは違うアプローチです：コンソールを右から左の読み上げ順序に変更し、通常の順序でリストを印刷します。それらは後方に表示されます。実際のデータを逆の順序で訪問することは、問題の制約のようには思えません。

Answer 5

ほとんどの答えを理解しました。リンクされたリストを元の位置に戻し、リストを最初に戻して印刷します。それが恒久的に破壊されないようにするには、リンク先のリストを元に戻して印刷するように、のリンクリストを逆にします。ただし、これは、実行スレッドが1つだけの場合、またはトラバーサル全体がクリティカルセクションになるため、一度に1つのスレッドのみが実行する場合にのみ機能します（つまり、2つ目のスレッドは決して再生できません）。トラバーサルの途中のリスト）。

Answer 6

これはインタビューの質問かもしれませんが、実際はweisアルゴリズムの本の背後にある質問です。再帰は一定のスペースを使用しないため、再帰を使用することはできません（インタビュアーが非表示にして明らかにするもの）。解決策は、逆の印刷と逆の逆です。