LeetCode — Add Two Numbers

Problem Link: https://leetcode.com/problems/add-two-numbers/

Example of question

Problem Description: 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 contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Approach Used: Linked List, Recursion

Explanation: In this question, two numbers are represented as a linked list such that each node of the linked list holds one digit of the number. What we have to do is add the two numbers and store the resultant number again as a linked list with each of the output digit in one node. The question has been made easier by storing the number in reverse order and hence the problem can simply be solved by a tail recursion.
The most naive way of doing this question would be to construct the original numbers first from the linked lists then simply add them. And finally, again separate digits of output and store them as a linked list.
But we can do better than that by simply adding digits and storing them into another node. Then call the same function for remaining digits. We just need to take care of one more thing, that if sum becomes a double-digit number then there will be a carry to the next node until we reach a node where the combined sum of both digits and carry is less than 10. I’ll show both iterative and recursive code for this question for better understanding.

Code: (Java)
Recursive:

public ListNode addTwoNumbersRecursive(ListNode l1, ListNode l2, int carry){
        //if we exhausted both the numbers
        if(l1==null && l2==null){
            //and there is no carry, then sum is completed
            if(carry==0)
                return null;
            //we will have additional node with carry data and then sum is completed
            //this will occur when for eg. sum of two 3 digit numbers is a 4 digit number
            else
                return new ListNode(carry);
        }
        
        int data1=0, data2=0;
        ListNode next1=null, next2=null;
        //if any of the list has been completed then it will just have null values
        if(l1!=null){
            data1 = l1.val;
            next1 = l1.next;
        }
        if(l2!=null){
            data2 = l2.val;
            next2 = l2.next;
        }
        
        int sum = data1+data2+carry;
        
        ListNode l3 = new ListNode(sum%10);//taking out last digit to make the node
        l3.next = addTwoNumbersRecursive(next1, next2, sum/10); // sending second last digit as carry for next node
        
        return l3;
    }
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return addTwoNumbersRecursive(l1, l2, 0);
        // return addTwoNumbersIterative(l1,l2);
    }

Iterative:

public ListNode addTwoNumbersIterative(ListNode l1, ListNode l2){
        int carry=0;
        ListNode l3 = null, result=null;//we will send result and keep changing l3
        
        while(l1!=null &&l2!=null){//until both list are non-empty
            int sum = l1.val+l2.val+carry;
            if(l3==null){//if list not created yet
                l3 = new ListNode(sum%10); //create list
                result=l3; //store head as result
            }
            else{
                l3.next = new ListNode(sum%10);//if list not null, store current digit as its next
                l3=l3.next;//move to next digit
            }
            carry = sum/10; //calculate carry for next iteration
            l1=l1.next;//increment both lists
            l2=l2.next;
        }
        //if any one of the list still remaining, add that and carry to output
        //same logic as above, just remove the other list
        while(l1!=null){
            int sum = l1.val+carry;
            if(l3==null){
                l3 = new ListNode(sum%10);
                result=l3;
            }
            else{
                l3.next = new ListNode(sum%10);
                l3=l3.next;
            }
            carry = sum/10;
            l1=l1.next;
        }
        while(l2!=null){
            int sum = l2.val+carry;
            if(l3==null){
                l3 = new ListNode(sum%10);
                result=l3;
            }
            else{
                l3.next = new ListNode(sum%10);
                l3=l3.next;
            }
            carry = sum/10;
            l2=l2.next;
        }
        //for extra digit with carry data
        if(carry!=0)
            l3.next = new ListNode(carry);
        
        return result;
    }
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // return addTwoNumbersRecursive(l1, l2, 0);
        return addTwoNumbersIterative(l1,l2);
    }

Complexity:
Space Complexity: O(max(m,n)+1). The sum will have digits at most 1 greater than the number of digits in greater number.
Time Complexity: O(max(m,n)+1). We will traverse both lists simultaneously until one of the lists is exhausted. Then we will traverse remaining nodes of the greater number. And finally, once we will visit to make a node for carry, so +1.
Here m,n are the number of digits in each number.