Add Two Numbers LinkedList| Solution

3. Add Two Numbers LinkedList

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.

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

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.

Solution

Algorithm:

1. Create a dummy node result
   .
2. Create two ListNode first and second and assign them l1 and l2.
3. Create two variable for maintaining divider and remainder and initialise with 0
4. While any of the ListNode not null, we will loop.
   1. Calculate sum, remainder, divider for each iteration from two lists.
      • sum = firstValue + secondValue + divider
      • divider = sum / 10
      • remainder = sum % 10
   2. Assign remainder to next of response and shift response pointer to it’s next
   3. Shift first and second to it’s next
5. If in the last divide has a value we we add it to next to response
6. Return result (dummy node)’s next.

/**
 * 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) {
        ListNode result = new ListNode();
        ListNode first = l1;
        ListNode second = l2;
        int divider = 0;
        int remainder = 0;
        ListNode response = result;
        while(first!=null || second!=null){
            int firstValue = (first!=null)?first.val:0;
            int secondValue = (second!=null)?second.val:0;

            int sum = firstValue + secondValue + divider;
            divider = sum / 10;
            remainder = sum % 10;
            response.next = new ListNode(remainder);
            response = response.next;
            if(first!=null) first = first.next;
            if(second!=null) second = second.next;
        }
        
        if(divider > 0){
            response.next = new ListNode(divider);
        }
        
        return result.next;
    }
}

Complexity :

Time :

O(max(m,n)) – Assume that m and n represents the length of l1 and l2 respectively, the algorithm above iterates at most max(m, n) times.

Space :

O(max(m,n)) –  O(max(m, n)) The length of the new list is at most max(m,n) + 1