Pythonとハッシュテーブルを使用してリンクリストの最後からn番目のノードを見つけよう

Question

私はちょうどデータ構造とアルゴリズムの学習を始めています。 Narasimha Karumanchi（CareerMonk）の "Pythonでのデータ構造とアルゴリズム思考"の本を使用しています。

リンクリストのトピックで、練習問題の1つは、リンクリストの最後からn番目のノードを見つけることです。著者は、ハッシュテーブルを使用することがブルートフォースを強制するよりも優れた解決策であると述べています。

Screenshot from the book

著者は実装を残しています。私はPythonでこれをクラスメソッドまたは関数としてどのようにコード化するのだろうかと思います。つまり、C/C++でメモリアドレスを取得するのは比較的簡単ですが、著者が提案するようにハッシュテーブル（辞書）を構築する方法はわかりません。

誰でも手助けできますか？

おかげで、Pythonで

Answer 1

、あなただけのキーがリンクされたリスト内のインデックスされている辞書を構築するだろう、と値がリスト自身のノードです。ノードの実際のメモリアドレスを知る必要はありません。ノードに辞書を追加してもそのノードのコピーは作成されず、元のオブジェクトへの別の参照が作成されるためです。

だからあなたのコードのようなコレクションのいくつかの種類でスタートします：

linked_index_to_node = {} 

そして、リンクリスト内の各項目について、それはこのようにそれを追加します。

# Making some assumptions about what your list looks like here 
next_node = linked_list 
next_index = 1 
while next_node is not None: 
    linked_index_to_node[next_index] = next_node 
    next_index += 1 
    next_node = next_node.next