在本文中，我们给出了一个链表，其中包含从 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
#include
using namespace std;
class Node {
public:
int value;
Node* next;
Node(int value) {
this->value = value;
next = NULL;
}
};
void solve(Node* head) {
set 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 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
