Add two numbers represented by Linked List

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

Example 1

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

Output:
  Resultant list: 6 → 1 → 3

Example 2
Input:
  First List: 1 →  5 →  1 →  8
  Second List: 3 →  6 →  9 →  8 →  7

Output
  Resultant list: [3] →  [8] →  [5] →  [0] → [5] 

 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 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.

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

Node.Java

package algorithm.linkedlist;

public class Node<T> {

    T data;
    Node next;

    public Node(T data) {
        this.data = data;
        this.next = null;
    }

    public void print() {
        String printValue = "[ " + this.data + "] ";
        if (next != null) {
            printValue += "---> ";
        }
        System.out.print(printValue);
    }
}

LinkedList.java

package algorithm.linkedlist;

public class LinkedList {

    private Node head;

    public LinkedList(Node node) {
        this.head = node;
    }

    public void add(Node node) {
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = node;
    }
}

Now traverse both lists. One by one pick nodes of both lists and add the values. If 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.

TwoNumber.java
package algorithm.linkedlist;

public class TwoNumber {

    public Node add(Node<Integer> head1, Node<Integer> head2) {
        if (head1 == null)
            return head2;
        if (head2 == null)
            return head1;

        Node head = new Node(0);
        Node current = head;
        int advance = 0;
        while (head1 != null && head2 != null) {
            int sum = head1.data + head2.data + advance;
            advance = sum / 10;
            sum = sum % 10;
            current.next = new Node(sum);
            current = current.next;
            head1 = head1.next;
            head2 = head2.next;
        }

        if (head1 != null) {
            if (advance == 0) {
                current.next = head1;
            } else {
                current.next = add(head1, new Node<>(advance));
            }
        } else if (head2 != null) {
            if (advance == 0) {
                current.next = head2;
            } else {
                current.next = add(head2, new Node<>(advance));
            }
        }
        return head.next;
    }
}

Now let us test the program:

package algorithm.linkedlist;

public class Test {

    public static void main(String[] args) {
        Node head1 = new Node(1);
        LinkedList list1 = new LinkedList(head1);
        list1.add(new Node(5));
        list1.add(new Node(1));
        list1.add(new Node(8));

        Node head2 = new Node(3);
        LinkedList list2 = new LinkedList(head2);
        list2.add(new Node(6));
        list2.add(new Node(9));
        list2.add(new Node(8));
        list2.add(new Node(7));

        Node head3 = LinkedListUtil.reverse(head1);
        Node head4 = LinkedListUtil.reverse(head2);

        TwoNumber twoNumber = new TwoNumber();
        Node head5 = twoNumber.add(head3, head4);
        head5 = LinkedListUtil.reverse(head5);
        LinkedListUtil.print(head5);
    }
}

Output of the program is:

[3] →  [8] → [5] → [0] → [5] 

We have used the reverse and print method from LinkedListUtil class for implementing the algorithm.

package algorithm.linkedlist;

public class LinkedListUtil {

    public static Node reverse(Node head) {
        if (head == null) {
            return null;
        }
        Node current = head;
        Node previous = null;
        while (current != null) {
            Node next = current.next;
            current.next = previous;
            previous = current;
            current = next;
        }
        return previous;
    }

    public static void print(Node head) {
        Node temp = head;
        while (temp != null) {
            temp.print();
            temp = temp.next;
        }
    }

    public static void newLine(){
        System.out.println();
    }
}

 

core java 12 Algorithm 12

FOLLOW US ON LinkedIn



Explore Tutu'rself