1. 找出两个链表的公共结点 【问题描述】给定两个单链表，编写算法找出两个链表的公共结点。 【输入形式】 四行： 第一行：一个数字（第一个单链表中的元素个数） 第二行：第一个单链表中各个结点的值 第三行：一个数字（第二个单链表中的元素个数） 第四行：第二个单链表中各个结点的值 【输出形式】 两行： 第一行：两个单链表的公共元素个数 第二行：依次打印输出各个公共元素 【样例输入】 6 12 5 8 9 -23 16 4 16 21 9 3 【样例输出】 2 9 16 注：若两个链表无公共元素，则输出： 0 没有公共元素 【样例说明】 写代码

#include <iostream>
#include <unordered_set> // 使用unordered_set存储链表节点，便于查找
using namespace std;

struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* findCommonNode(ListNode* pHead1, ListNode* pHead2) {
unordered_set<ListNode*> nodeSet;
ListNode* p1 = pHead1;
ListNode* p2 = pHead2;
while (p1 != nullptr) {
nodeSet.insert(p1);
p1 = p1->next;
}
while (p2 != nullptr) {
if (nodeSet.count(p2)) {
return p2;
}
p2 = p2->next;
}
return nullptr;
}

int main() {
int n1, n2;
cin >> n1;
ListNode* pHead1 = new ListNode(0); // 创建头结点
ListNode* p1 = pHead1;
for (int i = 0; i < n1; i++) {
int val;
cin >> val;
p1->next = new ListNode(val);
p1 = p1->next;
}
cin >> n2;
ListNode* pHead2 = new ListNode(0); // 创建头结点
ListNode* p2 = pHead2;
for (int i = 0; i < n2; i++) {
int val;
cin >> val;
p2->next = new ListNode(val);
p2 = p2->next;
}
ListNode* commonNode = findCommonNode(pHead1->next, pHead2->next);
if (commonNode == nullptr) {
cout << "0" << endl;
cout << "没有公共元素" << endl;
}
else {
int count = 0;
while (commonNode != nullptr) {
count++;
commonNode = commonNode->next;
}
cout << count << endl;
commonNode = findCommonNode(pHead1->next, pHead2->next);
while (commonNode != nullptr) {
cout << commonNode->val << " ";
commonNode = commonNode->next;
}
cout << endl;
}
return 0;
}