リンクリストで表される数値に 1 を加算します。

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

数値を表すこのリンク リストに 1 を追加するには、リスト内の最下位ビットの値をチェックする必要があります。 9 より小さい場合は問題ありませんが、それ以外の場合はコードによって次の番号などが変更されます。

次に、これを行う方法を理解するための例を見てみましょう。1999 年は (1->9->9 ->9) として表され、1 を追加すると (2->0-> 0) に変更されます。 ->0)

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

以上がリンクリストで表される数値に 1 を加算します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。