0

This problem requires me to find the intersection of two linked list. I created two maps with <int,ListNode*> pair. I want to check for common key value pair. The list is not sorted.

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_map <int,ListNode*> mp;
        unordered_map <int,ListNode*> m;
        while(headA != NULL){
            mp[headA->val] = headA;
            headA = headA ->next;
        }
        
        while(headB != NULL){
            m[headB->val] = headB;
            headB = headB ->next;
        }
//I have to make changes here
}
Evg
  • 25,259
  • 5
  • 41
  • 83
Deepak Kumar
  • 53
  • 7
  • 2
    What is wrong with the obvious approach of taking the keys of one map and checking for each if it exists in the other map? – Botje Jul 16 '21 at 15:28
  • Not clear what you mean by "common key/value". Values in those maps are pointers to `ListNode` and they do not intersect obviously – Slava Jul 16 '21 at 15:28
  • Are the list sorted? If so, there is `std::set_intersection` and friends that you can use. – NathanOliver Jul 16 '21 at 15:38
  • If your two lists are sorted (or you sort them beforehand), the intersection can be determined by a quite simple but efficient algorithm: In a loop: as longs as the first element of the first set is lower than the first element of the second drop it. As long as the first element of the second set is lower than the first element of the first drop it. The third case is that both are equal (common in both sets) and one of them has to be kept. There is `std::set_intersection()` and I made a destructive version of it in [this answer](https://stackoverflow.com/a/45079226/7478597) (FYI). – Scheff's Cat Jul 16 '21 at 15:38
  • @Botje it is inefficient as it result in a complexity of O(n*m), n and m being the lengths of both list. – Deepak Kumar Jul 16 '21 at 15:41
  • And what happens when one or the other list has the same value in it, more than once? unordered_map will not work at all, for this. The correct approach involves implementing the algorithm by yourself. There are very few non-trivial tasks that C++ will do for you, or has a ready-made function that makes the answer pop out. In nearly all cases you will need to implement yourself using the C++ library merely as convenient tools and algorithm that get used to implement the non-trivial task at hand. – Sam Varshavchik Jul 16 '21 at 15:44
  • @DeepakKumar unordered_maps have O(1) lookup, so O(n) or O(m) depending on which map you take the first key from. – Botje Jul 16 '21 at 15:44

1 Answers1

1

Using map will cause you an O(n) space complexity, it's better to get the lengths of both the lists and then move the head of the list which is longer by the amount of its extra longness. The time complexity for the following approach is O(n + m) and space complexity is O(1).

int getLengthLL(ListNode* head){
    int cnt = 0;
    while(head){
        head = head->next;
        cnt++;
    }
    return cnt;
}

ListNode* getIntersectionLL(ListNode* l1, ListNode* l2){
    int n1 = getLengthLL(l1);
    int n2 = getLengthLL(l2);
    
    while(n1 > n2){
        l1 = l1->next;
        n1--;
    }
    
    while(n2 > n1){
        l2 = l2->next;
        n2--;
    }
    
    while(l1 and l2){
        if(l1 == l2){
            return l1;
        }
        l1 = l1->next;
        l2 = l2->next;
    }
    
    return nullptr;
}
ubaid shaikh
  • 453
  • 3
  • 7