C++ program: Replace duplicate nodes in linked list with copies

In this article, we are given a linked list containing elements from 1 to n with duplicates. Elements 1 to n will always exist with duplicates in [1..n]. We need to replace each repeated element with n 1, n 2, etc.

Let us consider an example

1→2→2→4→5→3→6→6

Next n = 42. Therefore, each duplicate is replaced by n 1, n 2, etc. The next 42 is replaced with 47, the next 46 is replaced with 48, and the first instance remains intact.

First, we need to construct a binary tree in the main method, as shown below -

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);

Now the nodes are as follows;

1→2→7→4→5→3→6→8

As we have observed, we need to keep track of the elements we see to find the starting value of n. We also need a mechanism to determine which elements are repeated to replace their values.

The proposed data structure that immediately comes to mind has been identified. We can iterate over the linked list and push elements into the collection. After pushing the elements from the set, we can find the last element, which is the largest element available in the linked list, since sets are sorted data structures.

In the second traversal of the linked list, we can use the set as a hash. We will search for every element in the collection, two situations may occur.

• We find the element in the collection, then remove it from the collection and mark it.

• We did not find the element in the set, which means we have seen it from option one and we will replace it with the next n.

Example

To replace nodes with duplicate values ​​in a linked list, please follow the C program below. The C implementation utilizes a collection data structure to traverse the linked list, thus facilitating the search for duplicate elements.

#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;
}

Output

Before: 41 42 42 44 45 43 46 46
After: 41 42 47 44 45 43 46 48  

in conclusion

We used the concept of hashing and found the largest element in the linked list with the help of a set of data structures. We can also use map or unordered_map as hash.

The above is the detailed content of C++ program: Replace duplicate nodes in linked list with copies. For more information, please follow other related articles on the PHP Chinese website!