package linkedlist;

public class AddTwoIntegers {


    /*
     * Given head pointers of two linked lists where each linked list represents an integer number
     * (each node is a digit), add them and return the resulting linked list.
     * Input: List1: 1,2,3  List: 1,2
     * Output: 2, 4, 3
     *
     * Runtime Complexity:
     * Linear, O(n)
     *
     * Memory Complexity:
     * Constant, O(1)
     *
     * Add the integers 9901 and 237. The result of this addition would be 10138.
     * */

    static LinkedList.Node addIntegers(LinkedList.Node integer1,
                                       LinkedList.Node integer2) {

        LinkedList.Node result = null;
        LinkedList.Node last = null;
        int carry = 0;

        while (
                integer1 != null ||
                        integer2 != null ||
                        carry > 0) {

            int first = (integer1 == null ? 0 : integer1.data);
            int second = (integer2 == null ? 0 : integer2.data);
            int sum = first + second + carry;
            LinkedList.Node pNew = new LinkedList.Node(sum % 10);
            carry = sum / 10;
            if (result == null) {
                result = pNew;
            } else {
                last.next = pNew;
            }

            last = pNew;
            if (integer1 != null) {
                integer1 = integer1.next;
            }
            if (integer2 != null) {
                integer2 = integer2.next;
            }
        }
        return result;
    }

    protected static class LinkedList {

        private Node head;

        public Node head() {
            return head;
        }

        public void printNode(Node node) {
            while (node != null) {
                System.out.print(node.data + " ");
                node = node.next;
            }
        }

        /* Inserts a new Node at end of the list. */
        public void push(int new_data) {
            Node newNode = new Node(new_data);
            if (head == null) {
                head = new Node(new_data);
                return;
            }

            newNode.next = null;
            Node last = head;
            while (last.next != null) {
                last = last.next;
            }
            last.next = newNode;
        }

        public static class Node {
            private Node next;
            private Integer data;

            public Node(Integer data) {
                this.data = data;
            }

            public Node next() {
                return next;
            }

            public void setNext(Node next) {
                this.next = next;
            }

            public Integer data() {
                return data;
            }

            public void setData(Integer data) {
                this.data = data;
            }
        }
    }


    public static void main(String[] args) {

        LinkedList linkedList1 = new LinkedList();
        linkedList1.push(1);
        linkedList1.push(2);
        linkedList1.push(3);


        LinkedList linkedList2 = new LinkedList();
        linkedList2.push(1);
        linkedList2.push(2);

        System.out.println("List 1: ");
        linkedList1.printNode(linkedList1.head);
        System.out.println();

        System.out.println("List 2: ");
        linkedList2.printNode(linkedList2.head);
        System.out.println();

        LinkedList.Node mergedList = addIntegers(linkedList1.head, linkedList2.head);
        linkedList1.printNode(mergedList);
    }
}