Add Two Numbers Stored in Two Linked Lists in Reverse Order

We are given two linked lists that store the digits of two numbers in reverse order, where each node in the given linked list represents a digit of the number. We then find the sum of these two numbers and return it as a linked list.

For example, given linked lists list1 and list2 that store the digits of numbers 342 and 465, we return a linked list containing the digits of 807, as shown below.

Constraints:

• The number of nodes in each linked list is in the range [1, 100].
  
• 0 <= Node.val <= 9
• It is guaranteed that the list represents a number that does not have leading zeros.

We are given a class for a linked list, as shown below:

 public class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }

Since the digits are stored in reverse order, the units, tens, and hundreds places are represented by the first, second, and third nodes, respectively, and so on.

To solve this problem, we need to take digits from both linked lists one by one, add them, and store the result as nodes in the resulting linked list. The full code for solving this problem is given below:

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2){
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        int rest = 0;
        while (l1!=null || l2!=null || rest!=0){
            int sum = rest;
            if(l1!=null) {
                sum += l1.val;
                l1 = l1.next;
            }
            if(l2!=null){
                sum += l2.val;
                l2 = l2.next;
            }
            ListNode node = new ListNode(sum%10);
            current.next = node;
            current = node;
            rest = sum/10;
        }
        return dummy.next;
    }

We have created three variables:

1. The first variable (dummy) is used to keep a reference to return the root node.
   
2. The second (current) is used for appending nodes containing digits of the sum one by one.
3. The third variable (rest) is used to carry any value that remains after summing the digits of both numbers.

ListNode dummy = new ListNode(0);
ListNode current = dummy;
int rest = 0;

We run a while loop until either of the linked lists has remaining digits to add or the rest variable contains a carry value:

while (l1!=null || l2!=null || rest!=0){

We initialize a sum variable with rest as the initial value to account for any carry-over. Then, we take digits from each number (if available), add them to sum, and update the linked list nodes accordingly:

int sum = rest;
if(l1!=null) {
  sum += l1.val;
  l1 = l1.next;
}
if(l2!=null){
  sum += l2.val;
  l2 = l2.next;
}

Next, we create a new node with sum % 10 to store the current digit of the resulting number, append it as the next node, update the current node, and keep any carry-over value in the rest variable:

ListNode node = new ListNode(sum%10);
current.next = node;
current = node;
rest = sum/10;

Finally, we return dummy.next, which contains the summed number as a linked list:

return dummy.next;

This is the step-by-step process for adding two numbers represented as linked lists and returning the sum as a linked list. I hope you enjoyed reading this post.

Happy Coding!