user2962678 user2962678 - 1 month ago 9
Python Question

Find the nth node from the end of a Linked List using Python and hash table

I am just beginning learning Data Structures and Algorithms. I am using the "Data Structure and Algorithmic Thinking with Python" book by Narasimha Karumanchi(CareerMonk).

On the topic of linked lists, one of the exercise question is to find the nth node from the end of a linked list. The author mentions that using a hash table is a better solution than brute forcing it.

Screenshot from the book

The author has left the implementation out. I am wondering how will I code this in Python as a class method or a function. I mean, it is relatively easy to get the memory address in C/C++ but I don't know how to construct the hash table(dictionary) as the author suggests in the book.

Can anyone help?

Thanks

Answer

In Python, you would just construct a dictionary where the keys are indices in the linked lists, and the values are nodes in the lists themselves. You don't need to know the actual memory address of the nodes, since adding them to the dictionary won't create a copy of them, but rather another reference to the original object.

So your code would start out with some kind of collection like:

linked_index_to_node = {}

Then for each item in the linked list, it would add it like this:

# 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