リンクリストとして表される番号に1を追加しますか？

番号のリンクリスト表現は、リンクリストのすべてのノードが番号の1桁として扱われるように提供されます。ノードは、リンクリストの最初の要素が数値の最上位桁を保持し、リンクリストの最後の要素が数値の最下位ビットを保持するように数値を格納します。たとえば、番号202345は、リンクリストで（2-> 0-> 2-> 3-> 4-> 5）として表されます。

そして、このリンクリストで表される数値に1を追加するには、リストの最下位ビットの値を確認する必要があります。 9未満であれば問題ありません。そうでない場合、コードは次の桁を変更します。

それを行う方法を知るための例を見てみましょう。1999は（1-> 9-> 9-> 9）として表され、それに1を追加すると（2-> 0-> 0-> 0）<に変更されます。 / P>

Input:1999
Output:2000

説明

リンクリストとして表される特定の番号に1を追加するには、次のいくつかの手順に従うことを意味します。

• リンクリストを逆にする：リンクリストを逆にする必要があります。これは、最後の桁を最初に、最初を最後に変更することを意味します。たとえば、1-> 9->9->9は9->9->9->1に変換されます。
• この変更されたリンクリストについては、リストをトラバースし、左端のノードに1つ追加します。このノードの値が9に等しい場合は、キャリーを次のノードに伝播します。キャリーが来るまで同じ手順を実行します。
• 文字列を元の形式と同じように逆にしてから、頭を戻して文字列を印刷します。

例

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