将一个以链表表示的数字加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;
}