Add two numbers represented by Linked List

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.

Visualization of the addition of two numbers: (342 + 465 = =807). 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.

package com.tuturself.linkedlist;

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;
    }
}

Now let us test the program. Please use the Linked List Basic Operations article to have the basic operations of the LinkedList.

package com.tuturself.linkedlist;

public class TestLinkedList {

    public static void main(String[] args) {
        LinkedList list1 = new LinkedList(1);
        list1.add(3);
        list1.add(5);
        list1.add(7);
        list1.add(9);

        LinkedList list2 = new LinkedList(2);
        list2.add(4);
        list2.add(6);
        list2.add(8);
        list2.add(1);

        System.out.println("First List >>");
        list1.print();
        System.out.println("\nSecond List >>");
        list2.print();
        AddTwoNumbers addTwoNumbers = new AddTwoNumbers();
        LinkedList result = new LinkedList(0);
        result.head = addTwoNumbers.add(list1.head,list2.head);
        System.out.println("\nSum >>");
        result.print();
    }
}

The output of the program is:

First List >>
1->3->5->7->9->NULL
Second List >>
2->4->6->8->1->NULL
Sum >>
3->7->1->6->1->1->NULL

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.

 

Amazon Algorithm Microsoft Linked List