Add Two Numbers

Given two number represent by LinkedListcalculate the sum of the numbers and store the result in a new LinkedList. Each node of the linked list is represented by single-digit and the head node is the most significant digit. For Example:

Example:

Input:
  First List: 3 → 6 → 5 
  Second List: 2 → 4 → 8

Output: (365 + 248) = 613
  Resultant list: 6 → 1 → 3

Intuition

First, we need to reverse both the linked list. Keep track of the carry using a variable and simulate digits-by-digits sum starting from the head of list, which contains the least-significant digit.

Add Two Numbers represented by Linked Lists

Visualization of the addition of two numbers: (56712 + 6359 = 63,071). Each node contains a single digit and the digits are stored in reverse order.

Algorithm:

  • Create two LinkedList which will represent the above two numbers.
  • Reverse both the linked list.
  • Add two node values (Each node is being represented as single-digit)  starting from heads of two LinkedList.
  • If the sum is of above two node values is more than 10, then forward the carry.
  • Follow basic mathematical rules for addition.
  • Once the addition is done then reverse the resultant LinkedList and return.

Just like how you would sum two numbers on a piece of paper, we begin by summing the least-significant digits, which is the head of l1 and l2. Since each digit is in the range of 0…9, summing two digits may “overflow”.

For example (5 + 7 =12). In this case, we set the current digit to 2 and bring over the carry = 1 to the next iteration. Carry must be either 0 or 1 because the largest possible sum of two digits (including the carry) is (9 + 9 + 1 = 19).

Following is the LinkedList ADT  ListNode we are going to use it to solve the problem.

public class ListNode {
    int val;
    public ListNode next;

    public ListNode(int x) {
        val = x;
    }
}

Now traverse both lists. One by one pick nodes of both lists and add the values. If the sum is more than 10 then make carry as 1 and reduce sum. If one list has more elements than the other then consider remaining values of this list as 0. Following is the implementation of this approach.

public class AddTwoNumbers {

    public ListNode add(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode head = new ListNode(0);
        ListNode current = head;
        int advance = 0;
        while (l1 != null && l2 != null) {
            int sum = l1.val + l2.val + advance;
            advance = sum / 10;
            sum = sum % 10;
            current.next = new ListNode(sum);
            current = current.next;
            l1 = l1.next;
            l2 = l2.next;
        }

        if (l1 != null) {
            if (advance == 0) {
                current.next = l1;
            } else {
                current.next = add(l1, new ListNode(advance));
            }
        } else if (l2 != null) {
            if (advance == 0) {
                current.next = l2;
            } else {
                current.next = add(l2, new ListNode(advance));
            }
        }
        // when both the lists are finished but still the carry
        // is greater than 0. Example is (5+5) = 10
        else if (l1 == null && l2 == null && advance > 0) {
            current.next = new ListNode(advance);
        }
        return head.next;
    }
}

Complexity Analysis

  • Time complexity : O(max(m,n)). Assume that m and n represent the length of l1 and l2 respectively, the algorithm above iterates at most max(m,n) times.
  • Space complexity : O(max(m,n)). The length of the new list is at most max(m,n)+1.

Categories: Linked List

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s