给定两个链表 A 和 B,找到它们的交集 C。例如,A = [1,3,2], B = [5,1,4,2], C = [1,2]。 这个问题可以使用哈希表来解决。遍历链表 A,将 A 中所有元素加入哈希表 setA 中。然后遍历链表 B,将 B 中所有元素在 setA 中查找,如果存在,则将该元素加入结果链表 C 中。最后返回链表 C 即可。
时间: 2024-02-13 07:01:47 浏览: 54
是的,您说的很对。这是一种解决两个链表交集问题的常见方法。下面是一个简单的 C++ 实现:
```
#include <iostream>
#include <unordered_set>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
unordered_set<ListNode*> setA;
ListNode* currA = headA;
while (currA != nullptr) {
setA.insert(currA);
currA = currA->next;
}
ListNode* currB = headB;
while (currB != nullptr) {
if (setA.count(currB)) {
return currB;
}
currB = currB->next;
}
return nullptr;
}
int main() {
ListNode *A = new ListNode(1);
A->next = new ListNode(3);
A->next->next = new ListNode(2);
ListNode *B = new ListNode(5);
B->next = new ListNode(1);
B->next->next = new ListNode(4);
B->next->next->next = new ListNode(2);
ListNode *C = getIntersectionNode(A, B);
while (C != nullptr) {
cout << C->val << " ";
C = C->next;
}
return 0;
}
```
这个算法的时间复杂度是 O(m+n),其中 m 和 n 分别是链表 A 和 B 的长度。由于需要使用哈希表存储链表 A 中的元素,因此空间复杂度也是 O(m)。
阅读全文