用c++写出:已知两个单链表 LA 和 LB 分别表示两个集合,其元素递增排序,设计算法求出 LA 和 LB 的交集 C ,要求 C 同样以元素递增的单链表形式存储。
时间: 2023-10-30 19:10:06 浏览: 96
以下是用C++实现的代码:
```c++
#include <iostream>
using namespace std;
// 定义单链表节点结构体
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
// 求两个有序链表的交集
ListNode* getIntersection(ListNode* LA, ListNode* LB) {
ListNode dummy(0); // 定义一个虚拟头节点
ListNode* tail = &dummy; // 定义一个尾节点指针
while (LA && LB) { // 当两个链表都不为空时
if (LA->val < LB->val) {
LA = LA->next; // LA指针指向下一个节点
} else if (LA->val > LB->val) {
LB = LB->next; // LB指针指向下一个节点
} else { // LA->val == LB->val
tail->next = new ListNode(LA->val); // 新建节点并加入到尾节点后面
tail = tail->next; // 尾节点指向新加入的节点
LA = LA->next; // LA指针指向下一个节点
LB = LB->next; // LB指针指向下一个节点
}
}
return dummy.next; // 返回交集链表的头节点指针
}
// 打印链表
void printList(ListNode* head) {
while (head) {
cout << head->val << " ";
head = head->next;
}
cout << endl;
}
int main() {
// 构造链表LA: 1->2->3->4->5
ListNode* LA = new ListNode(1);
LA->next = new ListNode(2);
LA->next->next = new ListNode(3);
LA->next->next->next = new ListNode(4);
LA->next->next->next->next = new ListNode(5);
// 构造链表LB: 2->4->6
ListNode* LB = new ListNode(2);
LB->next = new ListNode(4);
LB->next->next = new ListNode(6);
cout << "LA: ";
printList(LA);
cout << "LB: ";
printList(LB);
ListNode* C = getIntersection(LA, LB);
cout << "C: ";
printList(C);
return 0;
}
```
输出结果为:
```
LA: 1 2 3 4 5
LB: 2 4 6
C: 2 4
```
注:此代码没有考虑内存释放问题,实际使用时需要释放动态分配的内存。
阅读全文