Algorithm and Data Structure ( Add Two Numbers In Linked List)

     Add Two Numbers

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.

Method 1:
   
This problem is straightforward where we need to traverse both the list simultaneously till we
reach the end of both the list.
Then we need to add the value of each respective node say x+y along with any carry.
Initialize carry with 0.
sum = x+y+carry

Create a new node and add sum Mod 10 as the value of the new node.
Update carry = sum/10

E.g   2 + 5 = 7  carry = 0, new node = 7,
        4+6= 10, carry=1, new node =0,
        3+4+1(carry), carry = 0, new node = 8

Output : 7=>0=>8

Remember to check any carry left after you traverse both the list till the end.
If carry > 0 then create a new node with carry as node value.

Implementation :

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */

 public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
       
       ListNode head = new ListNode(0); // dummy node
       ListNode output = head;
       int carry = 0;
       int sum=0;
           
            while (l1!= null || l2!= null)
            {
                sum = carry; // in each iteration initialize sum with any carry left
                if (l1 != null)
                {
                    sum +=  l1.val; // add node  value in sum
                    l1 = l1.next;  // move list1
                }
                if (l2 != null)
                {
                    sum+= l2.val; // add node  value in sum
                    l2 = l2.next;   // move list2
                }
              
                carry = sum/10;  // find any carry
                output.next = new ListNode(sum % 10); // create a new node with value
                output = output.next;
               
               
            }
             
                if (carry!=0)  // if any carry left than add it as new node value
                {
                     output.next = new ListNode(carry);
                     output = output.next;    
                }

            return head.next; // head is a dummy node whose next points to out output list.
       
    }

Time Complexity: O(max(m,n)) where m and n is the size of lists.
Space Complexity : O(max(m,n) + 1), here +1 is for any carry if left.

Method 2 :

There are other ways also where you traverse each list and form the number.
After forming the number, you add the two numbers and create the list in reverse order.
For forming the number you can use place value of each number in list

e.g 2=>4=>3 

2 * 10^0 + 4* 10^1 + 3* 10^2 = 2 + 40 + 300 = 342 

5 * 10^0 + 6* 10^1 + 4* 10^2 = 5 + 60 + 400 = 465 
                                                                     sum= 807

Create the list for each digit from sum in reverse order 7=>0=>8

Time Complexity : O(max(m,n)) +  O(max(m,n) + 1) where m and n is the size of lists.

= 2O(max(m,n))+1

Time is twice because first, we create the respective sum for each list in O(max(m,n)) and then
 break the sum in O(max(m,n)+1) time for creating output list.

Space Complexity : O(max(m,n) + 1), here +1 is for any carry if left.