How do I store addresses in a map in C++?

user_13629148 0
Viewed 1089

I'm trying to find the intersection point between two linked lists. I already know how to solve the problem by calculating the absolute difference in length of the two lists and displacing one of the pointers.

I want to know if it is possible to solve the question by storing addresses of each of the nodes along with a visited count in the map stores how many times the node has been visited.

int findMergeNode(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) {
    map<int,int>m1;
    //map<int*,int>m1 ??
    //map<address,int>m1??
    SinglyLinkedListNode *temp = head1;
    while(temp!=nullptr) {
        m1[temp]++;
        temp = temp->next;
    }
    temp = head2;
    while(temp!=nullptr) {
        m1[temp]++;
        temp = temp->next;
    }
    for(auto it=m1.begin();it!=m1.end();it++) {
        if(it->second > 1) {
            temp = it->first;
            return temp->data;
        } 
    }
    return 0;
}
linked-list dictionary c++
2 Answers
map<SinglyLinkedListNode *, int> m1;

will do the trick. For each pointer to a SinglyLinkedListNode, you keep a number, the number of visits.

You can do even better with:

map<const SinglyLinkedListNode *, int> m1;

If you don't need to iterate over the pointers in order, another option is:

unordered_map<const SinglyLinkedListNode *, int> m1;

Some might claim this to be better as pointers don't have a useful order.

user_44742300

The obvious solution might be to use:

std::map<SinglyLinkedListNode const *, int> m;

However, this suggests that the relative ordering of the pointers that are used as keys has some meaning, which is not the case here (and rarely ever is).

A slightly better solution would be to use:

std::unordered_map<SinglyLinkedListNode const *, int> m;

which suggests (correctly) that only uniqueness of the pointer values used as keys is relevant, and not their relative ordering.

user_83728530
Related