在本文中，我们给出了一个链表，其中包含从 1 到 n 的元素以及重复项。元素 1 到 n 将始终与 [1..n] 中的重复项存在。我们需要用 n+1、n+2 等替换每个重复元素。
让我们考虑一个例子
1→2→2→4→5→3→6→6
接下来 n = 42。因此，每个重复项都会被替换为 n+1、n+2 等。接下来的 42 被替换为 47，接下来的 46 被替换为 48，第一个实例保持原样。
首先，我们需要在main方法中构造一个二叉树，如下所示 -
Node* head = new Node(1); head->next = new Node(2); head->next->next = new Node(2); head->next->next->next = new Node(4); head->next->next->next->next = new Node(5); head->next->next->next->next->next = new Node(3); head->next->next->next->next->next->next = new Node(6); head->next->next->next->next->next->next->next = new Node(6); solve(head);
现在节点如下；
1→2→7→4→5→3→6→8
正如我们所观察到的，我们需要跟踪我们看到的元素以找到 n 的起始值。我们还需要一种机制来确定哪些元素被重复以替换它们的值。
立即想到的拟议数据结构已确定。我们可以遍历链表并将元素推入集合中。将集合中的元素压入后，我们可以找到最后一个元素，即链表中可用的最大元素，因为集合是排序的数据结构。
在链表的第二次遍历中，我们可以使用集合作为哈希。我们将搜索集合中的每个元素，可能会出现两种情况。
我们在集合中找到该元素，然后将其从集合中删除，并对其进行标记。
我们在集合中没有找到该元素，这意味着我们已经从选项一中看到了它，我们将用下一个 n 替换它。
要实现替换链表中重复值的节点，请按照下面的 C++ 程序进行操作。 C++ 实现利用集合数据结构来遍历链表，从而有助于搜索重复元素。
#include <iostream>
#include <set>
using namespace std;
class Node {
public:
int value;
Node* next;
Node(int value) {
this->value = value;
next = NULL;
}
};
void solve(Node* head) {
set<int> hash;
Node* copy = head;
while(copy) {
hash.insert(copy->value);
copy = copy->next;
}
auto it = hash.end();
it--;
int startingN = *it +1;
while(head) {
if(hash.find(head->value) != hash.end()) {
hash.erase(head->value);
} else {
head->value = startingN++;
}
head = head->next;
}
}
void printList(Node* head) {
while(head) {
cout << head->value << " ";
head = head->next;
}
}
int main() {
Node* head = new Node(41);
head->next = new Node(42);
head->next->next = new Node(42);
head->next->next->next = new Node(44);
head->next->next->next->next = new Node(45);
head->next->next->next->next->next = new Node(43);
head->next->next->next->next->next->next = new Node(46);
head->next->next->next->next->next->next->next = new Node(46);
cout << "Before: ";
printList(head);
cout << "\n";
solve(head);
cout << "After: ";
printList(head);
return 0;
}
Before: 41 42 42 44 45 43 46 46 After: 41 42 47 44 45 43 46 48
我们使用了哈希的概念，并借助数据结构集找到了链表中最大的元素。我们还可以使用 map 或 unordered_map 作为哈希。
以上是C++程序：将链表中的重复节点替换为副本的详细内容。更多信息请关注PHP中文网其他相关文章！
