how to find a loop in alinked list with the hash table method…
Make a hash or a map having key as the address of the node and a bool value to check if the node has already been visited or not.
map<struct node *, bool> m;
while traversing, if m[temp] is not visited(i.e. m[temp] is 0), then mark it as visited and if its already set to 1, that means we have come back again to the same node and hence there exists a loop.
3 Likes
how to implement it in c language i.e. without stl ?
i was doing this by taking an hash array and address of the nodes as index of hash array with values 1.if a value 2 occurs then break…but errors occur.so can you please suggest me how to do in this way?
Either define the array as struct node *visit[no_of_nodes], where array contains the addresses of nodes. i.e. visit[0]= address of head, visit[1]= address of head->next and so on. Then while inserting nodes, traverse the visit array upto the number of nodes inserted and check if the visit array contains the address of the node we are pointing at.Else , you can do the reverse way, i.e. make the array address serve as your index but that is likely to give run time error.