Add 1 to a number represented as linked list | Recursive Java 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
class GfG { static class Node { int data ; Node next ; } static Node newNode ( int data ) { Node new_node = new Node ( ) ; new_node . data = data ; new_node . next = null ; return new_node ; } static int addWithCarry ( Node head ) { if ( head == null ) return 1 ; int res = head . data + addWithCarry ( head . next ) ; head . data = ( res ) % 10 ; return ( res ) / 10 ; } static Node addOne ( Node head ) { int carry = addWithCarry ( head ) ; if ( carry > 0 ) { Node newNode = newNode ( carry ) ; newNode . next = head ; return newNode ; } return head ; } static void printList ( Node node ) { while ( node != null ) { System . out . print ( node . data ) ; node = node . next ; } System . out . println ( ) ; } public static void main ( String [ ] args ) { Node head = newNode ( 1 ) ; head . next = newNode ( 9 ) ; head . next . next = newNode ( 9 ) ; head . next . next . next = newNode ( 9 ) ; System . out . print ( " List ▁ is ▁ " ) ; printList ( head ) ; head = addOne ( head ) ; System . out . println ( ) ; System . out . print ( " Resultant ▁ list ▁ is ▁ " ) ; printList ( head ) ; } }