使用Python和hash tab从链接列表的末尾查找第n个节点

Question

我刚刚开始学习数据结构和算法。我使用的是Narasimha Karumanchi（CareerMonk）的“用Python进行数据结构和算法思考”一书。在

关于链表的主题，练习题之一是从链表的末尾找到第n个节点。作者提到，使用哈希表比强制使用哈希表更好。在

Screenshot from the book

作者省略了实现。我想知道如何在Python中将其作为类方法或函数进行编码。我的意思是，在C/C++中获取内存地址相对容易，但我不知道如何构造哈希表（字典）。在

有人能帮忙吗？在

谢谢

Answer 1

在Python中，只需构造一个字典，其中键是链接列表中的索引，而值是列表中的节点。您不需要知道节点的实际内存地址，因为将它们添加到字典中不会创建它们的副本，而是创建对原始对象的另一个引用。在

所以你的代码应该从某种集合开始，比如：

linked_index_to_node = {}

然后，对于链接列表中的每个项目，它将按如下方式添加：

^{pr2}$