在表示为链表的数字上加1？

数字的链表表示形式以将链表的所有节点都视为数字的一位的方式提供。节点存储该数字，以使链表的第一个元素保持该数字的最高有效位，而链表的最后一个元素保持该数字的最低有效位。例如，数字202345在链接列表中表示为（2-> 0-> 2-> 3-> 4-> 5）。

要向此链表表示的数字中添加一个，我们必须检查列表的最低有效位的值。如果小于9则可以，否则代码将更改下一个数字，依此类推。

现在让我们看一个例子来知道如何做，1999表示为（1-> 9-> 9-> 9），并加上1应该将其更改为（2-> 0-> 0-> 0）

Input:1999
Output:2000

说明

要将1加到表示为链表的给定数字上，意味着要执行一些步骤，

• 反转链表：您需要反转链表，这意味着将最后一位更改为第一位，将第一位更改为最后一位。例如，将1-> 9-> 9-> 9转换为9-> 9-> 9-> 1。

• 对于此已更改的链接列表，现在遍历该列表，在最左侧的节点中添加一个。如果此节点的值等于9，则将进位传播到下一个节点。执行相同的步骤，直到携带到位。

• 将字符串恢复为原始形式，然后返回头部以打印字符串。

示例

#include <iostream>
using namespace std;
//n =下一个节点 d =数据 p =上一个节点；h =头节点；c =当前节点
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;
}