Add Two Numbers

• A simple approach could be to recursively add the nodes of the linked list while keeping track of the carry generated.
• The idea behind this approach is the same as finding the sum of two numbers manually on a paper, where we start by adding the LSD and move on till the MSD. Also, keeping track of the carry generated in every iteration.
• As the linked lists represent the numbers in reverse order, the LSD occurs at the starting of the list and MSD occurs at the ending.
• So to perform the addition, we can add the corresponding nodes (i.e. nodes present at the same position) of the two linked lists to generate the resulting digit in the sum list.
• While adding, it is possible that the sum of the two nodes is greater than 9. This will generate a carry that needs to be added to the next significant digit.
• In case one of the lists has more number elements than the other, then we consider the remaining values of the other list as 0.

The steps are as follows:

• Let the recursive function be addTwoNumbersHelper('node1', 'node2', 'carry') which takes the current node of the first list, the current node of the second list, and the carry generated from the previous iteration/addition.
• Initially, we call the function as addTwoNumbersHelper('num1', 'num2', 0).
• Base Condition: If 'node1' = NULL AND 'node2' = NULL AND 'carry' = 0, return NULL.
• Let 'val1' and 'val2' denote the value stored in the current nodes of the two linked lists, respectively. And 'next1' and 'next2' denote the pointers to the node present after the current nodes of the two linked lists, respectively.
• If 'node1' = NULL, then the list 1 is empty so consider the current node’s value as zero i.e. 'val1' = 0, and the node after the current node as NULL i.e. 'next1' = NULL.
• Otherwise, list 1 is not empty. So, 'val1' = 'node1'.data and 'next1' = 'node1'.next.
• If 'node2' = NULL, then the list 2 is empty so consider the current node’s value as zero i.e. 'val2' = 0 and the node after the current node as NULL i.e. 'next2' = NULL.
• Otherwise, list 2 is not empty. So, 'val2' = 'node2'.data  and 'next2' = 'node2'.next.
• Add the values in the current nodes of the two linked lists along with the carry to generate the resulting sum. Store it in a variable, say sum i.e. 'sum' = 'val1' + 'val2' + 'carry'.
• Get the next node of the sum list by creating a new node having data = 'sum'%10. Store the new node in a variable say, 'sumNode'.
• Recursively call the function to generate the remaining nodes of the sum list as:
  • 'sumNode'.next = addTwoNumbersHelper('next1', 'next2', 'sum' / 10)
• Return 'sumNode'.

• The idea behind this approach is exactly similar to the previous approach. But here, instead of using recursion, we add the two linked lists iteratively.

The steps are as follows:

• Let 'node1' and 'node2' denote the current node of the first list and the second list, respectively.
• Initially, 'node1' = 'num1' and 'node2' = 'num2'
• Create two variables ‘sum’ and 'carry' which will be used to store the sum and carry generated in the current iteration and initialize them with zero.
• Repeat the following steps until both the lists are exhausted i.e. 'node1' != NULL OR 'node2' != NULL:
  • Set 'sum' = 'carry'.
  • If 'node1' != NULL, then list 1 is not exhausted. So, add the current node’s value to the sum i.e. 'sum' = 'sum' + 'node1'.data. And move to the next node of the list i.e. 'node1' = 'node1'.next.
  • If 'node2' != NULL, then list 2 is not exhausted. So, add the current node’s value to the sum i.e. 'sum' = 'sum' + 'node2'.data. And move to the next node of the list i.e. 'node2' = 'node2'.next.
  • Get the next node of the sum list by creating a new node having data = 'sum' % 10. And add this node to the sum list.
  • Set 'carry' = 'sum' / 10.
• If 'carry' = 1, add a new node to the sum list having data = 1.
• Return the head of the sum list.

1. The idea behind this approach is exactly similar to the previous approach. But here, instead of creating a new list for storing the sum, we use any one of the two linked lists to store the sum list.
2. Note: Here we have used the first linked list to store the sum list. We can also use the second list but the idea will remain the same.

The Steps are as follows:

• Let 'node1' and 'node2' denote the current node of the first list and the second list, respectively.
• Initially, 'node1' = 'num1' and 'node2' = 'num2'
• Create two variables ‘sum’ and ‘carry’ which will be used to store the sum and carry generated in the current iteration and initialize them with zero.
• Create another variable 'prev' to store the previous node of the linked list, and initialize it with NULL.
• Repeat the following steps until any one the lists is exhausted i.e. 'node1' != NULL and 'node2' != NULL:
  • Add the values in the current nodes of the two linked lists along with the carry to generate the resulting sum i.e. ‘sum’ = 'node1'.data + 'node2'.data + 'carry'.
  • Store the next node of the sum list in the first linked list by updating the current node’s data value as 'node1'.data = ‘sum’ % 10.
  • Update the carry as 'carry' = ‘sum’ / 10.
  • Keep track of the previous node by setting 'prev' = 'node1'.
  • Move to the next node:
    • 'node1' = 'node1'.next
    • 'node2' = 'node2'.next
• Check any of list contain the remaining digits, i.e. if 'node1' != NULL or 'node2' != NULL:
  • We need to add the remaining digits to the sum list.
  • If 'node2' != NULL, list 1 is empty and list 2 contains the remaining digits. So, set 'prev'.next = 'node2'.
  • Set, 'node1' = 'prev'.next.
  • Add the remaining digits to the sum list by repeating the following operation until 'node1' becomes NULL:
    • ‘sum’ = 'node1'.data + 'carry'
    • Store the next digit by updating the current node’s data value 'node1'.data = ‘sum’ % 10.
    • Update the carry as 'carry' = ‘sum’ / 10.
    • Keep track of the previous node by setting 'prev' = 'node1'.
    • Move to the next node, 'node1' = 'node1'.next
• Now, we have added both lists. But it is possible that carry is generated from the last iteration. So, if 'carry' > 0, add a new node to the sum list having data = ‘carry’.
• Return the head of the sum list i.e. 'num1'.