3

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;
}
Shrenik Raj
  • 33
  • 4
  • Did you try compiling and running the code? What happens when you do that? – cigien Aug 24 '20 at 17:51
  • Now if your second map has a million nodes and the first node is the intersection point, you wastefully go through that entire second linked list. – PaulMcKenzie Aug 24 '20 at 17:54
  • @PaulMcKenzie Agreed but my question was intended more towards storing addresses in a map and not efficiency per se. Wouldn't have noticed it without your saying so, though. – Shrenik Raj Aug 24 '20 at 17:56
  • @ShrenikRaj Remember that the comment section is for comments, not answers. I commented on your code and approach. – PaulMcKenzie Aug 24 '20 at 17:57
  • There is `std::set_intersection` if you want that. – Ranoiaetep Aug 24 '20 at 19:05

2 Answers2

5
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.

Jeffrey
  • 11,063
  • 1
  • 21
  • 42
1

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.

cigien
  • 57,834
  • 11
  • 73
  • 112
  • Nitpick, map use `class Compare = std::less`, not `<`. But yeah, it's still UB. A conversion to `uintptr_t` might help? – Jeffrey Aug 24 '20 at 18:10
  • Why do you say it's UB? This seems to indicate it should be fine: https://stackoverflow.com/a/1418152/23649 – jtbandes Aug 24 '20 at 18:11
  • https://quuxplusone.github.io/blog/2019/01/20/std-less-nightmare/ – Jeffrey Aug 24 '20 at 18:12
  • although, in practice, for normal platforms, I've never had an issue using < on pointers – Jeffrey Aug 24 '20 at 18:13
  • @jtbandes Hmm, I'm not completely sure. I'll have to dig deeper. Also, I'm not saying comparing pointers is UB, just unspecified. UB comes from not satisfying the requirements of `map`. But I might be wrong. – cigien Aug 24 '20 at 18:15
  • But since that map uses `std::less`, doesn't that mean it gets a strict total order, even if the built-in `<` might not provide a total order? – jtbandes Aug 24 '20 at 18:22
  • @jtbandes Yes, this seems to be the case. While the ordering might be different for different runs of the program, the requirements of `map` are still satisfied. I'll edit the answer, thanks. – cigien Aug 24 '20 at 18:25