// D. Scott
// CCI - Problem 2.5
// Calculate sum of numbers in 2 linked lists (digits reversed)
//  and store result in third linked list (recursive solution)

class Node {
    Node next = null;
    int data;
    
    public Node(int d) {
        data = d;
        next = null;
    }

    void appendToTail(int d) {
        Node end = new Node(d);
        Node n = this;
        while (n.next != null) {
            n = n.next;
        }
        n.next = end;
    }
}

public static void main (String[] args)
{
    Node l1 = new Node(9);
    Node l1h = l1;
    l1.appendToTail(9);
    l1.appendToTail(9);
    
    // print first list:
    System.out.println("\nList 1 (first term):")
    while (l1 != null) {
        System.out.print(l1.data + " ");
        l1 = l1.next;
    }
    l1 = l1h;

    Node l2 = new Node(2);
    Node l2h = l2;
    l2.appendToTail(1);
    l2.appendToTail(3);
    l2.appendToTail(1);
    l2.appendToTail(4);

    // print second list:
    System.out.println("\n\nList 2 (second term):")
    while (l2 != null) {
        System.out.print(l2.data + " ");
        l2 = l2.next;
    }
    l2 = l2h;
    
    // third list to store the sum
    Node l3 = new Node(0);
    Node l3_head = l3;
    
    sum(l1,l2,l3,0);
    l3 = l3_head.next;
        
    Node rev_l3 = new Node(0);
    reverseList(l3,rev_l3);
    rev_l3 = rev_l3.next;
    
    // print sum:
    System.out.println("\n\nSum:")
    while (rev_l3 != null) {
        System.out.print(rev_l3.data+" ");
        rev_l3 = rev_l3.next;
    }
        
}

void reverseList(Node l, Node r) {
    if (l == null)
        return;
    reverseList(l.next,r);

    r.appendToTail(l.data);
}

void sum(Node l1, Node l2, Node l3, int c) {
    if (l1 == null && l2 == null) {
        return;
    } else {
        int term1 = 0;
        int term2 = 0;
        int carry = 0;
        Node n1 = l1;
        Node n2 = l2;
        if (l1 != null) {
            term1 = l1.data;
            n1 = l1.next;
        }
        if (l2 != null) {
            term2 = l2.data;
            n2 = l2.next;
        }
        if (term1 + term2 + c > 9)
            carry = 1;
        sum(n1, n2, l3, carry);
        Node d = new Node((term1 + term2 + c)%10);
        l3.appendToTail(d.data);
    }
}

// D. Scott
// CCI - Problem 2.5 FOLLOW UP
// Calculate sum of numbers in 2 linked lists (digits not reversed)
//  and store result in third linked list (recursive solution)

class Node {
    Node next = null;
    int data;
    
    public Node(int d) {
        data = d;
        next = null;
    }

    void appendToTail(int d) {
        Node end = new Node(d);
        Node n = this;
        while (n.next != null) {
            n = n.next;
        }
        n.next = end;
    }
}

public static void main (String[] args)
{
    Node l1 = new Node(9);
    Node l1h = l1;
    l1.appendToTail(9);
    l1.appendToTail(9);
    
    // print first list:
    System.out.println("\nList 1 (first term):")
    while (l1 != null) {
        System.out.print(l1.data + " ");
        l1 = l1.next;
    }
    l1 = l1h;

    Node l2 = new Node(2);
    Node l2h = l2;
    l2.appendToTail(4);
    l2.appendToTail(1);
    l2.appendToTail(3);
    l2.appendToTail(1);

    // print second list:
    System.out.println("\n\nList 2 (second term):")
    while (l2 != null) {
        System.out.print(l2.data + " ");
        l2 = l2.next;
    }
    l2 = l2h;
    
    // third list to store the sum
    Node l3 = new Node(0);
    Node l3_head = l3;
    
    Node l1r = new Node(0);
    Node l2r = new Node(0);
    reverseList(l1,l1r);
    reverseList(l2,l2r);
    l1r = l1r.next;
    l2r = l2r.next;

    sum(l1r,l2r,l3,0);
    l3 = l3_head.next;
        
 //   Node rev_l3 = new Node(0);
 //   reverseList(l3,rev_l3);
 //   rev_l3 = rev_l3.next;
    
    // print sum:
    System.out.println("\n\nSum:")
    while (l3 != null) {
        System.out.print(l3.data+" ");
        l3 = l3.next;
    }
        
}

void reverseList(Node l, Node r) {
    if (l == null)
        return;
    reverseList(l.next,r);

    r.appendToTail(l.data);
}

void sum(Node l1, Node l2, Node l3, int c) {
    if (l1 == null && l2 == null) {
        return;
    } else {
        int term1 = 0;
        int term2 = 0;
        int carry = 0;
        Node n1 = l1;
        Node n2 = l2;
        if (l1 != null) {
            term1 = l1.data;
            n1 = l1.next;
        }
        if (l2 != null) {
            term2 = l2.data;
            n2 = l2.next;
        }
        if (term1 + term2 + c > 9)
            carry = 1;
        sum(n1, n2, l3, carry);
        Node d = new Node((term1 + term2 + c)%10);
        l3.appendToTail(d.data);
    }
}