2019-04-07

How do you add two numbers represented by linked lists ??

Problem statement:
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.

class Node {
    int data;
    Node next;

    Node(int data) {

        this.data = data;
    }

    Node() {

    }

    @Override

    public String toString() {
        return "Node{" +
                "data=" + data +
                ", next=" + next +
                '}';
    }
}

public class AddTwoNumbers {

    static Node head = null;

    public static void main(String[] args) {

        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);

        n1.next = n2;

        n2.next = n3;

        Node n4 = new Node(1);

        Node n5 = new Node(2);
        Node n6 = new Node(3);

        n4.next = n5;

        n5.next = n6;

        Node result = calculate(n1, n4);

        System.out.println(result);
    }

    static Node calculate(Node a, Node b) {

        //        //FIXME: Write your logic
        //  1, 2, 3
        //  1, 2, 3
        int carry = 0;

        while (a != null && b != null) {

            addLast(a.data + b.data);

            a = a.next;

            b = b.next;
        }
        return head;
    }

    public static void addLast(int data) {


        if (head == null) {

            head = new Node(data);
            return;
        }
        Node last = head;
        while (last.next != null) {
            last = last.next;
        }
        last.next = new Node(data);
    }
}


Output:
Node{data=2, next=Node{data=4, next=Node{data=6, next=null}}}

No comments:

Post a Comment