Number is represented in linked list such that each digit corresponds to a node in linked list. Add 1 to it. For example 1999 is represented as (1-> 9-> 9 -> 9) and adding 1 to it should change it to (2->0->0->0)

Below are the steps :

  1. Reverse given linked list. For example, 1-> 9-> 9 -> 9 is converted to 9-> 9 -> 9 ->1.
  2. Start traversing linked list from leftmost node and add 1 to it. If there is a carry, move to the next node. Keep moving to the next node while there is a carry.
  3. Reverse modified linked list and return head.

C++ prpgramming:

[pastacode lang=”cpp” manual=”%2F%2F%20C%2B%2B%20program%20to%20add%201%20to%20a%20linked%20list%0A%23include%3Cbits%2Fstdc%2B%2B.h%3E%0A%20%0A%2F*%20Linked%20list%20node%20*%2F%0Astruct%20Node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20Node*%20next%3B%0A%7D%3B%0A%20%0A%2F*%20Function%20to%20create%20a%20new%20node%20with%20given%20data%20*%2F%0ANode%20*newNode(int%20data)%0A%7B%0A%20%20%20%20Node%20*new_node%20%3D%20new%20Node%3B%0A%20%20%20%20new_node-%3Edata%20%3D%20data%3B%0A%20%20%20%20new_node-%3Enext%20%3D%20NULL%3B%0A%20%20%20%20return%20new_node%3B%0A%7D%0A%20%0A%2F*%20Function%20to%20reverse%20the%20linked%20list%20*%2F%0ANode%20*reverse(Node%20*head)%0A%7B%0A%20%20%20%20Node%20*%20prev%20%20%20%3D%20NULL%3B%0A%20%20%20%20Node%20*%20current%20%3D%20head%3B%0A%20%20%20%20Node%20*%20next%3B%0A%20%20%20%20while%20(current%20!%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20next%20%20%3D%20current-%3Enext%3B%0A%20%20%20%20%20%20%20%20current-%3Enext%20%3D%20prev%3B%0A%20%20%20%20%20%20%20%20prev%20%3D%20current%3B%0A%20%20%20%20%20%20%20%20current%20%3D%20next%3B%0A%20%20%20%20%7D%0A%20%20%20%20return%20prev%3B%0A%7D%0A%20%0A%2F*%20Adds%20one%20to%20a%20linked%20lists%20and%20return%20the%20head%0A%20%20%20node%20of%20resultant%20list%20*%2F%0ANode%20*addOneUtil(Node%20*head)%0A%7B%0A%20%20%20%20%2F%2F%20res%20is%20head%20node%20of%20the%20resultant%20list%0A%20%20%20%20Node*%20res%20%3D%20head%3B%0A%20%20%20%20Node%20*temp%2C%20*prev%20%3D%20NULL%3B%0A%20%0A%20%20%20%20int%20carry%20%3D%201%2C%20sum%3B%0A%20%0A%20%20%20%20while%20(head%20!%3D%20NULL)%20%2F%2Fwhile%20both%20lists%20exist%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Calculate%20value%20of%20next%20digit%20in%20resultant%20list.%0A%20%20%20%20%20%20%20%20%2F%2F%20The%20next%20digit%20is%20sum%20of%20following%20things%0A%20%20%20%20%20%20%20%20%2F%2F%20(i)%20Carry%0A%20%20%20%20%20%20%20%20%2F%2F%20(ii)%20Next%20digit%20of%20head%20list%20(if%20there%20is%20a%0A%20%20%20%20%20%20%20%20%2F%2F%20%20%20%20%20next%20digit)%0A%20%20%20%20%20%20%20%20sum%20%3D%20carry%20%2B%20head-%3Edata%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20update%20carry%20for%20next%20calulation%0A%20%20%20%20%20%20%20%20carry%20%3D%20(sum%20%3E%3D%2010)%3F%201%20%3A%200%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20update%20sum%20if%20it%20is%20greater%20than%2010%0A%20%20%20%20%20%20%20%20sum%20%3D%20sum%20%25%2010%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Create%20a%20new%20node%20with%20sum%20as%20data%0A%20%20%20%20%20%20%20%20head-%3Edata%20%3D%20sum%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Move%20head%20and%20second%20pointers%20to%20next%20nodes%0A%20%20%20%20%20%20%20%20temp%20%3D%20head%3B%0A%20%20%20%20%20%20%20%20head%20%3D%20head-%3Enext%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20if%20some%20carry%20is%20still%20there%2C%20add%20a%20new%20node%20to%0A%20%20%20%20%2F%2F%20result%20list.%0A%20%20%20%20if%20(carry%20%3E%200)%0A%20%20%20%20%20%20%20%20temp-%3Enext%20%3D%20newNode(carry)%3B%0A%20%0A%20%20%20%20%2F%2F%20return%20head%20of%20the%20resultant%20list%0A%20%20%20%20return%20res%3B%0A%7D%0A%20%0A%2F%2F%20This%20function%20mainly%20uses%20addOneUtil().%0ANode*%20addOne(Node%20*head)%0A%7B%0A%20%20%20%20%2F%2F%20Reverse%20linked%20list%0A%20%20%20%20head%20%3D%20reverse(head)%3B%0A%20%0A%20%20%20%20%2F%2F%20Add%20one%20from%20left%20to%20right%20of%20reversed%0A%20%20%20%20%2F%2F%20list%0A%20%20%20%20head%20%3D%20addOneUtil(head)%3B%0A%20%0A%20%20%20%20%2F%2F%20Reverse%20the%20modified%20list%0A%20%20%20%20return%20reverse(head)%3B%0A%7D%0A%20%0A%2F%2F%20A%20utility%20function%20to%20print%20a%20linked%20list%0Avoid%20printList(Node%20*node)%0A%7B%0A%20%20%20%20while%20(node%20!%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20printf(%22%25d%22%2C%20node-%3Edata)%3B%0A%20%20%20%20%20%20%20%20node%20%3D%20node-%3Enext%3B%0A%20%20%20%20%7D%0A%20%20%20%20printf(%22%5Cn%22)%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20above%20function%20*%2F%0Aint%20main(void)%0A%7B%0A%20%20%20%20Node%20*head%20%3D%20newNode(1)%3B%0A%20%20%20%20head-%3Enext%20%3D%20newNode(9)%3B%0A%20%20%20%20head-%3Enext-%3Enext%20%3D%20newNode(9)%3B%0A%20%20%20%20head-%3Enext-%3Enext-%3Enext%20%3D%20newNode(9)%3B%0A%20%0A%20%20%20%20printf(%22List%20is%20%22)%3B%0A%20%20%20%20printList(head)%3B%0A%20%0A%20%20%20%20head%20%3D%20addOne(head)%3B%0A%20%0A%20%20%20%20printf(%22%5CnResultant%20list%20is%20%22)%3B%0A%20%20%20%20printList(head)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D” message=”” highlight=”” provider=”manual”/]

Output:

List is 1999

Resultant list is 2000

 Recursive Implementation:
We can recursively reach the last node and forward carry to previous nodes. Recursive solution doesn’t require reversing of linked list. We can also use a stack in place of recursion to temporarily hold nodes.

C++ Programming:

[pastacode lang=”cpp” manual=”%2F%2F%20Recursive%20C%2B%2B%20program%20to%20add%201%20to%20a%20linked%20list%0A%23include%3Cbits%2Fstdc%2B%2B.h%3E%0A%20%0A%2F*%20Linked%20list%20node%20*%2F%0Astruct%20Node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20Node*%20next%3B%0A%7D%3B%0A%20%0A%2F*%20Function%20to%20create%20a%20new%20node%20with%20given%20data%20*%2F%0ANode%20*newNode(int%20data)%0A%7B%0A%20%20%20%20Node%20*new_node%20%3D%20new%20Node%3B%0A%20%20%20%20new_node-%3Edata%20%3D%20data%3B%0A%20%20%20%20new_node-%3Enext%20%3D%20NULL%3B%0A%20%20%20%20return%20new_node%3B%0A%7D%0A%20%0A%2F%2F%20Recursively%20add%201%20from%20end%20to%20beginning%20and%20returns%0A%2F%2F%20carry%20after%20all%20nodes%20are%20processed.%0Aint%20addWithCarry(Node%20*head)%0A%7B%0A%20%20%20%20%2F%2F%20If%20linked%20list%20is%20empty%2C%20then%0A%20%20%20%20%2F%2F%20return%20carry%0A%20%20%20%20if%20(head%20%3D%3D%20NULL)%0A%20%20%20%20%20%20%20%20return%201%3B%0A%20%0A%20%20%20%20%2F%2F%20Add%20carry%20returned%20be%20next%20node%20call%0A%20%20%20%20int%20res%20%3D%20head-%3Edata%20%2B%20addWithCarry(head-%3Enext)%3B%0A%20%0A%20%20%20%20%2F%2F%20Update%20data%20and%20return%20new%20carry%0A%20%20%20%20head-%3Edata%20%3D%20(res)%20%25%2010%3B%0A%20%20%20%20return%20(res)%20%2F%2010%3B%0A%7D%0A%20%0A%2F%2F%20This%20function%20mainly%20uses%20addWithCarry().%0ANode*%20addOne(Node%20*head)%0A%7B%0A%20%20%20%20%2F%2F%20Add%201%20to%20linked%20list%20from%20end%20to%20beginning%0A%20%20%20%20int%20carry%20%3D%20addWithCarry(head)%3B%0A%20%0A%20%20%20%20%2F%2F%20If%20there%20is%20carry%20after%20processing%20all%20nodes%2C%0A%20%20%20%20%2F%2F%20then%20we%20need%20to%20add%20a%20new%20node%20to%20linked%20list%0A%20%20%20%20if%20(carry)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20Node%20*newNode%20%3D%20new%20Node%3B%0A%20%20%20%20%20%20%20%20newNode-%3Edata%20%3D%20carry%3B%0A%20%20%20%20%20%20%20%20newNode-%3Enext%20%3D%20head%3B%0A%20%20%20%20%20%20%20%20return%20newNode%3B%20%2F%2F%20New%20node%20becomes%20head%20now%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20return%20head%3B%0A%7D%0A%20%0A%2F%2F%20A%20utility%20function%20to%20print%20a%20linked%20list%0Avoid%20printList(Node%20*node)%0A%7B%0A%20%20%20%20while%20(node%20!%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20printf(%22%25d%22%2C%20node-%3Edata)%3B%0A%20%20%20%20%20%20%20%20node%20%3D%20node-%3Enext%3B%0A%20%20%20%20%7D%0A%20%20%20%20printf(%22%5Cn%22)%3B%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20above%20function%20*%2F%0Aint%20main(void)%0A%7B%0A%20%20%20%20Node%20*head%20%3D%20newNode(1)%3B%0A%20%20%20%20head-%3Enext%20%3D%20newNode(9)%3B%0A%20%20%20%20head-%3Enext-%3Enext%20%3D%20newNode(9)%3B%0A%20%20%20%20head-%3Enext-%3Enext-%3Enext%20%3D%20newNode(9)%3B%0A%20%0A%20%20%20%20printf(%22List%20is%20%22)%3B%0A%20%20%20%20printList(head)%3B%0A%20%0A%20%20%20%20head%20%3D%20addOne(head)%3B%0A%20%0A%20%20%20%20printf(%22%5CnResultant%20list%20is%20%22)%3B%0A%20%20%20%20printList(head)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D” message=”” highlight=”” provider=”manual”/]

Output:

List is 1999

Resultant list is 2000