是否有在地图中查找公共键值对的功能或方法？

Question

这道题要求我求两个链表的交集。我用对创建了两个地图。我想检查公共键值对。列表未排序。

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

使用 map 会导致 O(n) space 的复杂度，最好先获取两个列表的长度，然后移动列表的头部，该头部更长，长度为它的额外长度.以下方法的时间复杂度为 O(n + m)，space 复杂度为 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;
}

是否有在地图中查找公共键值对的功能或方法？

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

c++

unordered-map

intersection

linked-list