C++-Programm: Ersetzen Sie doppelte Knoten in der verknüpften Liste durch Kopien

In diesem Artikel erhalten wir eine verknüpfte Liste mit Elementen von 1 bis n mit Duplikaten. Die Elemente 1 bis n sind immer mit Duplikaten in [1..n] vorhanden. Wir müssen jedes wiederholte Element durch n+1, n+2 usw. ersetzen.

Betrachten wir ein Beispiel

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

Nächstes n = 42. Daher wird jedes Duplikat durch n+1, n+2 usw. ersetzt. Die nächsten 42 werden durch 47 ersetzt, die nächsten 46 werden durch 48 ersetzt und die erste Instanz bleibt erhalten.

Zuerst müssen wir einen Binärbaum in der Hauptmethode erstellen, wie unten gezeigt -

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

Jetzt sind die Knoten wie folgt:

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

Wie wir beobachtet haben, müssen wir die Elemente, die wir sehen, im Auge behalten, um den Startwert von n zu ermitteln. Wir brauchen auch einen Mechanismus, um zu bestimmen, welche Elemente wiederholt werden, um ihre Werte zu ersetzen.

Die vorgeschlagene Datenstruktur, die einem sofort in den Sinn kommt, wird identifiziert. Wir können die verknüpfte Liste durchlaufen und Elemente in die Sammlung verschieben. Nachdem wir die Elemente in der Menge verschoben haben, können wir das letzte Element finden, das das größte verfügbare Element in der verknüpften Liste ist, da Mengen sortierte Datenstrukturen sind.

Beim zweiten Durchlauf der verknüpften Liste können wir die Menge als Hash verwenden. Wir werden nach jedem Element in der Sammlung suchen, es können zwei Situationen auftreten.

• Wir finden das Element in der Sammlung, entfernen es aus der Sammlung und markieren es.

• Wir haben das Element nicht im Set gefunden, was bedeutet, dass wir es bereits bei Option eins gesehen haben und es durch das nächste ersetzen werden.

Beispiel

Um Knoten durch doppelte Werte in einer verknüpften Liste zu ersetzen, befolgen Sie bitte das folgende C++-Programm. Die C++-Implementierung nutzt eine Sammlungsdatenstruktur zum Durchlaufen der verknüpften Liste und erleichtert so die Suche nach doppelten Elementen.

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

Ausgabe

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

Fazit

Wir haben das Konzept des Hashings verwendet und mithilfe einer Reihe von Datenstrukturen das größte Element in der verknüpften Liste gefunden. Wir können auch map oder unordered_map als Hash verwenden.

Das obige ist der detaillierte Inhalt vonC++-Programm: Ersetzen Sie doppelte Knoten in der verknüpften Liste durch Kopien. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!