Add two numbers represented by Linked List

Given two numbers represented by a linked list in reverse order.

You have two linked lists.

Each of them represent a number which is not empty and not negative.

Each of the node in the linked lists represent a single digit.

The numbers are linked in reverse order.

Create a linked list with their sum in the same reverse order.

For example,

Consider this example:

The first two linked lists represent the input .

The third one represents the output.

The first number is 342 in reverse order.

The second number is 465 in reverse order.

Try out the solution here:

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

Solution:

Let’s look at the logic of adding two numbers.

You start adding from the last digit of each of the numbers.

You add the two digits and then you take the carry over.

Then you add the last but one digit of both the numbers along with the carry over.

You keep on doing this until there are digits in both the numbers.

When one of the numbers is lesser than the other number ,

then you will run out of digits for that number.

At this time just add the digit of the other number along with the carry over.

If there is no carry over , just include the other digit.

Include the remaining digits of the bigger number as well just like above.

Since the given linked lists are already in reverse order , it is easy for us to do the above logic starting from the first nodes.

If you represent the above logic in code , it goes like this:

sum = carry over (initially 0) + last digit of first number (if present) + last digit of second number (if present)

For every iteration the last digit moves by one place.

Let’s code this:

/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        
        int sum=0;
        
        int carry = 0;
        
        
         ListNode result = new ListNode();
        
        ListNode node = result;
        
        while(l1 != null || l2 != null || carry!=0){
            
            node.next = new ListNode();
            
            node = node.next;
       
            sum = carry + (l1!=null?l1.val:0) +(l2!= null? l2.val:0) ;
            
            carry = sum /10;
            
             
            node.val = sum % 10;
            
            l1 = l1!=null?l1.next:l1;
            
            l2 = l2!=null?l2.next:l2;
            
                
        }
       
        return result.next;
        
    }
}

Let’s examine the code.

We create a root node called result which we are going to return as the output.

We create another node which points to the root node initially.

We will use this node as a pointer and keep moving along during the addition.

Since we need to return the root node we create this second pointer node.

 ListNode result = new ListNode();
        
        ListNode node = result;

We perform the addition as long as one of the linked list is null or there is a carry value.

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

Then we prepare the linked list node:

 node.next = new ListNode();
            
 node = node.next;
       

Why do we move to the next node of the current node initially itself?

Why not at the end of the iteration?

If we do at the end of the iteration then we should add a null check to make sure that atleast one of the linked list is not null or the carry over is not zero:

       if(!(l1 == null && l2 == null && carry ==0)){
                
                node.next = new ListNode();
                node = node.next;
            }
            
            

So we can avoid that check.

Once we prepare the node we need to find the sum and the carry over.

The carry over is found out by dividing the sum by 10.

The output digit is found out by finding the modulus of sum and 10.

Once we find the output digit we move to the next node.

Here is the entire code again:

/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        
        int sum=0;
        
        int carry = 0;
        
        
         ListNode result = new ListNode();
        
        ListNode node = result;
        
        while(l1 != null || l2 != null || carry!=0){
            
            node.next = new ListNode();
            
            node = node.next;
       
            sum = carry + (l1!=null?l1.val:0) +(l2!= null? l2.val:0) ;
            
            carry = sum /10;
            
             
            node.val = sum % 10;
            
            l1 = l1!=null?l1.next:l1;
            
            l2 = l2!=null?l2.next:l2;
            
                
        }
       
        return result.next;
        
    }
}

Finally we return the next node of the result node , since we moved the logic of moving to the next node to the beginning of the iteration as discussed earlier.

Time complexity:

The time complexity is O( m or n ) where m is the number of digits in the first linked list and n is the number of digits / nodes in the second linked list. Whichever is greater we need to consider that as we do that number of iterations.

Space complexity:

Space complexity is also O(m or n ) whichever is greater to create the output linked list.

That’s it!