Add 1 to a number represented by a linked list

The linked list representation of a number is provided as follows: all nodes of the linked list are considered as one digit of the number. Nodes store numbers such that the first element of the linked list holds the most significant digit of the number, and the last element of the linked list holds the least significant digit of the number. For example, the number 202345 is represented in the linked list as (2->0->2->3->4->5).

To add 1 to this linked list representing numbers, we must check the value of the least significant bit in the list. If it's less than 9 it's ok, otherwise the code will change the next number and so on.

Now let us see an example to understand how to do this, 1999 is represented as (1->9->9 ->9) and adding 1 should change it to (2->0-> 0->0)

Input:1999
Output:2000

Explanation

Add 1 to the number represented by the given linked list, which means you need to follow the following steps:

• Reverse Linked list: The linked list needs to be reversed, that is, the last number becomes the first, and the first becomes the last. For example, 1->9->9->9 translates to 9->9->9->1.
• For this reversed linked list, traverse the linked list and add 1 to the leftmost node. If the value of that node is equal to 9, then the carry is passed to the next node. Repeat this process until there are no carries.
• Restore the string to its original form, then return the head node to print the string.

Example

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

The above is the detailed content of Add 1 to a number represented by a linked list. For more information, please follow other related articles on the PHP Chinese website!