Add 1 to a number represented as linked list | Node class ; 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 program to test above function
class Node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . next = None NEW_LINE DEDENT DEDENT def newNode ( data ) : NEW_LINE INDENT new_node = Node ( 0 ) NEW_LINE new_node . data = data NEW_LINE new_node . next = None NEW_LINE return new_node NEW_LINE DEDENT def addWithCarry ( head ) : NEW_LINE INDENT if ( head == None ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT res = head . data + addWithCarry ( head . next ) NEW_LINE head . data = int ( ( res ) % 10 ) NEW_LINE return int ( ( res ) / 10 ) NEW_LINE DEDENT def addOne ( head ) : NEW_LINE INDENT carry = addWithCarry ( head ) NEW_LINE if ( carry != 0 ) : NEW_LINE INDENT newNode = Node ( 0 ) NEW_LINE newNode . data = carry NEW_LINE newNode . next = head NEW_LINE return newNode NEW_LINE DEDENT return head NEW_LINE DEDENT def printList ( node ) : NEW_LINE INDENT while ( node != None ) : NEW_LINE INDENT print ( node . data , end = " " ) NEW_LINE node = node . next NEW_LINE DEDENT print ( " " ) NEW_LINE DEDENT head = newNode ( 1 ) NEW_LINE head . next = newNode ( 9 ) NEW_LINE head . next . next = newNode ( 9 ) NEW_LINE head . next . next . next = newNode ( 9 ) NEW_LINE print ( " List ▁ is ▁ " ) NEW_LINE printList ( head ) NEW_LINE head = addOne ( head ) NEW_LINE print ( " Resultant list is   " ) NEW_LINE printList ( head ) NEW_LINE