# Add 1 to a number represented as linked list in C++

In this post, we will learn how to add 1 to a number represented as linked list in C++. For example 4959 is represented as (4-> 9-> 5 -> 9->9) and adding 1 to it should change it to (4->9->6->0->0).

## Add 1 to a number represented as linked list in C++

In this approach we will follow the following steps:

1. At first linked list is reversed.

2. Then we add 1 to leftmost node in the linked list. And if there is a carry, we will move to the next node. We will keep traversing until the carry is 0.

3. Finally we will again reverse our modified linked list and then return head.

#include <bits/stdc++.h> using namespace std; class Node { public: int data; Node* next; Node(int value){ data=value; next=NULL; } }; Node *reverse(Node *head) { Node * prev = NULL; Node * current = head; Node * next; while (current != NULL) { next = current->next; current->next = prev; prev = current; current = next; } return prev; } Node *addUtil(Node *head) { Node* res = head; Node *temp, *prev = NULL; int sum; int carry = 1; while (head != NULL) { sum = carry + head->data; carry = (sum >= 10)? 1 : 0; sum = sum % 10; head->data = sum; temp = head; head = head->next; } if (carry > 0) temp->next = new Node(carry); return res; } Node* add1One(Node *head) { head = reverse(head); head = addUtil(head); return reverse(head); } void printList(Node *node) { while (node != NULL) { cout << node->data; node = node->next; } cout<<endl; } int main() { Node *head = new Node(4); head->next = new Node(9); head->next->next = new Node(5); head->next->next->next = new Node(9); cout << "List is "; printList(head); cout<<endl; head = add1One(head); cout << "After adding 1 the new list is "; printList(head); return 0; }

input:List is 4959 output:After adding 1 the new list is 4960

## Leave a Reply