Addiere 1 zu einer Zahl, die durch eine verknüpfte Liste dargestellt wird

Die Darstellung einer Zahl in einer verknüpften Liste sieht folgendermaßen aus: Alle Knoten der verknüpften Liste werden als eine Ziffer der Zahl betrachtet. Knoten speichern Zahlen so, dass das erste Element der verknüpften Liste die höchstwertige Ziffer der Zahl enthält und das letzte Element der verknüpften Liste die niedrigstwertige Ziffer der Zahl enthält. Beispielsweise wird die Zahl 202345 in der verknüpften Liste als (2->0->2->3->4->5) dargestellt.

Um 1 zu dieser verknüpften Liste mit Zahlen hinzuzufügen, müssen wir den Wert des niedrigstwertigen Bits in der Liste überprüfen. Wenn es weniger als 9 ist, ist es in Ordnung, andernfalls ändert der Code die nächste Zahl und so weiter.

Sehen wir uns nun ein Beispiel an, um zu verstehen, wie das geht: 1999 wird als (1->9->9 ->9) dargestellt und das Hinzufügen von 1 sollte es in (2->0->0->0) ändern.

Input:1999
Output:2000

Erklärung

Fügen Sie 1 zu der durch die angegebene verknüpfte Liste dargestellten Zahl hinzu, was bedeutet, dass Sie die folgenden Schritte ausführen müssen:

• Verknüpfte Liste umkehren: Sie müssen die verknüpfte Liste umkehren, d. h. die letzte ändern Zahl zum Ersten, Der Erste wird zum Letzten. Beispielsweise wird 1->9->9->9 zu 9->9->9->1 übersetzt.
• Durchlaufen Sie für diese umgekehrt verknüpfte Liste die verknüpfte Liste und fügen Sie 1 zum Knoten ganz links hinzu. Wenn der Wert dieses Knotens gleich 9 ist, wird der Übertrag an den nächsten Knoten übergeben. Wiederholen Sie diesen Vorgang, bis keine Überträge mehr vorhanden sind.
• Stellen Sie die Zeichenfolge in ihrer ursprünglichen Form wieder her und geben Sie den Kopfknoten zurück, um die Zeichenfolge zu drucken.

Beispiel

#include <iostream>
using namespace std;
//n=next node ; d=data ; p= previous node; h=head node; c=current node
class Node {
   public:
      int d;
      Node* n;
};
Node *newNode(int d) {
   Node *new_node = new Node;
   new_node->d = d;
   new_node->n = NULL;
   return new_node;
}
Node *reverse(Node *h) {
   Node * p = NULL;
   Node * c = h;
   Node * n;
   while (c != NULL) {
      n = c->n;
      c->n = p;
      p = c;
      c = n;
   }
   return p;
}
Node *addOneUtil(Node *h) {
   Node* res = h;
   Node *temp, *p = NULL;
   int carry = 1, sum;
   while (h != NULL) {
      sum = carry + h->d;
      carry = (sum >= 10)? 1 : 0;
      sum = sum % 10;
      h->d = sum;
      temp = h;
      h = h->n;
   }
   if (carry > 0)
      temp->n = newNode(carry);
   return res;
}
Node* addOne(Node *h) {
   h = reverse(h);
   h = addOneUtil(h);
   return reverse(h);
}
int main() {
   Node *h = newNode(1);
   h->n = newNode(9);
   h->n->n = newNode(9);
   h->n->n->n = newNode(9);
   h = addOne(h);
   while (h != NULL) {
      cout << h->d;
      h = h->n;
   }
   cout<<endl;
   return 0;
}

Das obige ist der detaillierte Inhalt vonAddiere 1 zu einer Zahl, die durch eine verknüpfte Liste dargestellt wird. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!