is there a function or way to find common key value pair in a map?

Question

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
}

Answer 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;
}