Problem: Add Two Numbers — Leet code (Difficulty — Medium)

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Solution:

One of the basic solutions to this problem would be to iterate through each node and store the whole integers into a variable and then get the sum. Then separate the integer while creating a linked list out of it. The problem with this would be the inability of Integer to store a number with value higher than 2,147,483,647. Even unsigned or even double or long will have problems as the number goes up. Using BigInteger or BigDecimal are possible options but will make the code more complex. So how do we solve this?

We go to our most basic calculation of addition. The one we learn in our elementary school.

We add the last two digits, then carry over as needed and proceed in the same way. Here is the solution in code.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int carry = 0;
        int sum = 0;
        ListNode temp = new ListNode(0);
        ListNode startNode = temp;
        while(l1 != null || l2 != null){
            if(l1 == null) {
                sum = l2.val + carry;
                l2 = l2.next;
            } else if(l2 == null) {
                sum = l1.val + carry;
                l1 = l1.next;
            } else {
                sum = l1.val + l2.val + carry;
                l1 = l1.next;
                l2 = l2.next;
            }
            carry = sum/10;
            sum = sum %10;  
            temp.next = new ListNode(sum);
            temp = temp.next;
        }
        if (carry != 0){
            temp.next = new ListNode(carry);
        }
        return startNode.next; 
    }  
}

Notes:

The following condition in the while loop is to account for the difference in lengths of two integers.

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

This is to add the last carry over if any.

if (carry != 0){
            temp.next = new ListNode(carry);
        }

Full code at GitHub.

Credits to: https://leetcode.com/problems/add-two-numbers/