Ajouter 1 à un nombre représenté par une liste chaînée

La représentation en liste chaînée d'un nombre est fournie comme ceci : Tous les nœuds de la liste chaînée sont considérés comme un chiffre du nombre. Les nœuds stockent les nombres de telle sorte que le premier élément de la liste chaînée contienne le chiffre le plus significatif du nombre et que le dernier élément de la liste chaînée contienne le chiffre le moins significatif du nombre. Par exemple, le nombre 202345 est représenté dans la liste chaînée par (2->0->2->3->4->5).

Pour ajouter 1 à cette liste chaînée représentant des nombres, nous devons vérifier la valeur du bit le moins significatif de la liste. Si c'est moins de 9 c'est ok, sinon le code changera le numéro suivant et ainsi de suite.

Voyons maintenant un exemple pour comprendre comment procéder, 1999 est représenté par (1->9->9 ->9) et l'ajout de 1 devrait le changer en (2->0->0->0 )

Input:1999
Output:2000

Explication

Ajoutez 1 au nombre représenté par la liste chaînée donnée, ce qui signifie que vous devez suivre les étapes suivantes :

• Inverser la liste chaînée : Vous devez inverser la liste chaînée, c'est-à-dire changer le dernier numéro au premier, le premier devient le dernier. Par exemple, 1->9->9->9 se traduit par 9->9->9->1.
• Pour cette liste chaînée inversée, parcourez la liste chaînée et ajoutez 1 au nœud le plus à gauche. Si la valeur de ce nœud est égale à 9, alors le report est transmis au nœud suivant. Répétez ce processus jusqu'à ce qu'il n'y ait plus de report.
• Restaurez la chaîne à sa forme originale et renvoyez le nœud principal pour imprimer la chaîne.

Exemple

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!