algorithm - 数字のリンクリストに1を追加

Question

各ノードが数字からの数字であるようなリンクリストが与えられます。

例：番号が1234の場合、対応するリンクリストは次のとおりです。

1 -> 2 -> 3 -> 4 -> [\]

問題は、この数に1を加えることです。したがって、出力は次のようになります。

1 -> 2 -> 3 -> 5 -> [\]

O（n）空間でO（n）時間で再帰的に行うことができます。O（logn）時間計算量のソリューションを最適化することは可能ですか？

更新： nは合計桁数です。

Answer 1

いいえ、追加のデータ構造がない場合に限ります。

リストの最後のノードは常に変更され、アルゴリズムがそこに到達するまでにO（n）時間がかかるため（追加のデータ構造がない場合はリスト全体を追跡する必要があります）、O（n）が下位になります。バウンド。

Answer 2

何nですか？が桁数の場合n、解決策はないと思いますO(log(n))。

nが数値自体である場合、桁数はすでにO(log(n))です。

Answer 3

操作を実行する前に各番号をトラバースする必要があります。他の方法はありませんが、要素の総数がわかっているため、head-> next-> next->next...のようにすべての移動操作を記述できます。 forループの代わりに同じ行に。これにより、forループの実行による過負荷時間の複雑さが回避されるため、プロセスが高速化されます。