c++,给定n个整数,按输入顺序建立单链表,删除其中的重复数字,输出结果链表。(要求不可以构建新结点,不可以定义新链表。在原链表上删除。)
时间: 2024-09-15 14:08:16 浏览: 42
在C++中,如果你不能创建新的节点或新建链表,并且需要直接在原链表上删除重复的数字,你可以考虑使用哈希集合(如`std::unordered_set`)来跟踪已经遇到的数字,同时遍历链表。以下是简单的步骤:
1. 定义一个迭代器`current`用于遍历链表。
2. 当`current`所指的数字不在集合中时,将其添加到集合并移动到下一个节点。
3. 如果`current`所指的数字已经在集合中,则跳过该节点,即`current = current->next`。
以下是对应的C++代码实现:
```cpp
#include <iostream>
#include <unordered_set>
using namespace std;
// 假设已有一个名为ListNode的链表节点结构体,包含int val和指向下一个节点的指针next
void removeDuplicates(ListNode* head) {
unordered_set<int> seen;
ListNode *prev = nullptr, *current = head;
while (current != nullptr) {
if (seen.find(current->val) == seen.end()) {
seen.insert(current->val);
if (prev != nullptr) prev->next = current;
prev = current;
}
current = current->next;
}
// 将最后一个节点的next置为nullptr,结束循环
if (prev != nullptr) prev->next = nullptr;
}
// 示例链表节点的构造函数和打印链表功能
ListNode* createList(int n, int input[]) {
// 创建链表...
}
void printList(ListNode* head) {
// 打印链表...
}
int main() {
int n;
cin >> n;
int input[n];
// 输入n个整数...
ListNode* head = createList(n, input);
cout << "Original list: ";
printList(head);
removeDuplicates(head); // 删除重复元素
cout << "List after removing duplicates: ";
printList(head);
return 0;
}
```
阅读全文