求两个递增链表的差集,即存在于A中不存在于B中,要求用c加加进行类的封装,写出完整代码
时间: 2024-11-18 18:27:51 浏览: 22
2_链表_求la和lb的交集_
5星 · 资源好评率100%
在C++中,我们可以创建一个名为`ListNode`的结构体来表示链表节点,并编写一个名为`DiffSet`的类来处理求两个递增链表的差集操作。这里是一个完整的示例代码:
```cpp
#include <iostream>
using namespace std;
// 定义链表节点
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
class DiffSet {
private:
ListNode* head; // 差集头部
public:
// 添加元素到差集中
void insert(int num) {
if (!head || num > head->val) {
ListNode* newNode = new ListNode(num);
newNode->next = head;
head = newNode;
}
}
// 判断元素是否在差集中
bool contains(int num) {
ListNode* cur = head;
while (cur) {
if (cur->val == num)
return true;
cur = cur->next;
}
return false;
}
// 获取差集头节点并更新内部状态
ListNode* getDifference(ListNode* bHead) {
ListNode dummy(0); // 避免除空判断
ListNode* aTail = &dummy;
for (ListNode* bCur = bHead; bCur != nullptr; bCur = bCur->next) {
if (!contains(bCur->val)) {
aTail->next = bCur;
aTail = aTail->next;
}
}
// 移除与b链表相同的部分
if (head != &dummy && head->val == bHead->val) {
head = head->next;
}
return dummy.next; // 返回差集的第一个元素
}
};
int main() {
DiffSet diffSet;
// 假设我们有两段已排序的链表 A 和 B,这里仅作为演示例子
ListNode* aList = new ListNode(1);
aList->next = new ListNode(3);
aList->next->next = new ListNode(5);
ListNode* bList = new ListNode(2);
bList->next = new ListNode(4);
bList->next->next = new ListNode(6);
diffSet.insert(1);
diffSet.insert(3);
diffSet.insert(5);
// 现在 diffSet 包含 [1, 3, 5]
ListNode* result = diffSet.getDifference(bList);
while (result) {
cout << result->val << " ";
result = result->next;
}
return 0;
}
```
这个`DiffSet`类首先将输入的元素按照链表顺序添加到`head`,然后通过`getDifference`函数遍历`bList`,如果`bList`中的元素不在`diffSet`中,则将其添加到结果链表中。最后返回包含差集元素的新链表。
阅读全文