给定两个单链表,编写算法找出两个链表的公共结点。给出完整能运行的c++代码
时间: 2024-10-08 11:18:41 浏览: 17
在C++中,我们可以设计一个算法,通过比较两个链表的每个节点,找到第一个共同的节点。这里是一个解决方案,使用了哈希集合(unordered_set)来优化查找过程:
```cpp
#include <iostream>
#include <unordered_set>
// 链表节点类
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
// 找到两个链表的第一个公共节点
ListNode* findIntersectionNode(ListNode* headA, ListNode* headB) {
std::unordered_set<ListNode*> set;
// 将链表A的所有节点添加到哈希集中
while (headA != nullptr) {
set.insert(headA);
headA = headA->next;
}
// 从链表B开始,检查每个节点是否在哈希集中
headA = headB;
while (headA != nullptr && !set.count(headA)) {
headA = headA->next;
}
return headA;
}
// 测试代码
int main() {
// 创建两个示例链表
ListNode* list1 = new ListNode(4);
list1->next = new ListNode(1);
list1->next->next = new ListNode(8);
list1->next->next->next = new ListNode(4);
list1->next->next->next->next = new ListNode(5); // 重复节点
ListNode* list2 = new ListNode(5);
list2->next = new ListNode(0);
list2->next->next = new ListNode(1);
list2->next->next->next = new ListNode(8); // 公共节点
ListNode* intersection = findIntersectionNode(list1, list2);
if (intersection != nullptr) {
std::cout << "公共节点的值: " << intersection->val << std::endl;
} else {
std::cout << "没有公共节点" << std::endl;
}
delete list1;
delete list2;
return 0;
}
```
这段代码首先遍历链表A,将所有的节点添加到哈希集合中。然后,它从链表B的头部开始,如果遇到的节点已经在集合中,那么就找到了公共节点。