Add 1 to a number represented as linked list | Recursive C ++ program to add 1 to a linked list ; Linked list node ; Function to create a new node with given data ; Recursively add 1 from end to beginning and returns carry after all nodes are processed . ; If linked list is empty , then return carry ; Add carry returned be next node call ; Update data and return new carry ; This function mainly uses addWithCarry ( ) . ; Add 1 to linked list from end to beginning ; If there is carry after processing all nodes , then we need to add a new node to linked list ; New node becomes head now ; A utility function to print a linked list ; Driver code
#include <bits/stdc++.h> NEW_LINE struct Node { int data ; Node * next ; } ; Node * newNode ( int data ) { Node * new_node = new Node ; new_node -> data = data ; new_node -> next = NULL ; return new_node ; } int addWithCarry ( Node * head ) { if ( head == NULL ) return 1 ; int res = head -> data + addWithCarry ( head -> next ) ; head -> data = ( res ) % 10 ; return ( res ) / 10 ; } Node * addOne ( Node * head ) { int carry = addWithCarry ( head ) ; if ( carry ) { Node * newNode = new Node ; newNode -> data = carry ; newNode -> next = head ; return newNode ; } return head ; } void printList ( Node * node ) { while ( node != NULL ) { printf ( " % d " , node -> data ) ; node = node -> next ; } printf ( " STRNEWLINE " ) ; } int main ( void ) { Node * head = newNode ( 1 ) ; head -> next = newNode ( 9 ) ; head -> next -> next = newNode ( 9 ) ; head -> next -> next -> next = newNode ( 9 ) ; printf ( " List ▁ is ▁ " ) ; printList ( head ) ; head = addOne ( head ) ; printf ( " Resultant list is " printList ( head ) ; return 0 ; }