LinkedList addition

Add 2 linkedlists without reverse in O(n) and constant space.

eg: 1->2->3 + 1->7 = 1->4->0

Solution: recursion
1. 在短的list前面补0使得两个list一样长
2. recursively add two lists
3. 处理第一位，如果第一位是0，说明第一位原本>=10, 在前面加1
相似的leetcode问题：Add Two Numbers

public class LinkedListAddition {
    // carry must defined as global variable
    public static int carry = 0;
       
    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
        }
    }
       
    // create new node
    ListNode newNode(int x) {
        ListNode node = new ListNode(x);
        node.val = x;
        node.next = null;
        return node;
    }
       
    public static void main(String[] args) {
        LinkedListAddition list = new LinkedListAddition();
               
        // create 1->2->3
        ListNode l1 = list.newNode(1);
        l1.next = list.newNode(2);
        l1.next.next = list.newNode(3);

        // create 1->7
        ListNode l2 = list.newNode(1);
        l2.next = list.newNode(7);
               
        // print linkedlist
        System.out.println("Two input LinkedList: ");
        printLinkedList(l1);
        printLinkedList(l2);
               
        // insert 0 to make shorter list has the same length as the longer list
        int len1 = len(l1);
        int len2 = len(l2);
        int diff = Math.abs(len1 - len2);
        ListNode newL2;
        ListNode newL1;
        if (len1 > len2) {
            ListNode node = list.newNode(0);
            newL2 = node;
            diff--;
            while (diff > 0) {
                node.next = list.newNode(0);
                node = node.next;
                diff--;
            }
            node.next = l2;
            System.out.print("newL2: ");
            printLinkedList(newL2);
                       
            // recursively add two lists
            addList(l1, newL2);
        } else if (len1 < len2) {
            ListNode node = list.newNode(0);
            newL1 = node;
            diff--;
            while (diff > 0) {
                node.next = list.newNode(0);
                newL1 = node.next;
                diff--;
            }
            node.next = l1;
            System.out.print("newL1: ");
            printLinkedList(newL1);
                       
            // recursively add two lists
            addList(newL1, l2);
        } else {
            // recursively add two lists
            addList(l1, l2);
        }
                               
        System.out.print("After adding, l1 is: ");
        printLinkedList(l1);
               
        // if first digit is 0 means it is >= 10, need to deal with this carry
        if (l1.val == 0) {
            ListNode newHead = list.newNode(1);
            newHead.next = l1;
            System.out.print("Result: ");
            printLinkedList(newHead);
        }
    }
       
    public static ListNode addList(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l1;
        }
               
        addList(l1.next, l2.next);
 
        carry = l1.val + l2.val + carry;
        if (carry >= 10) {
            l1.val = carry - 10;
            carry = 1;
        } else {
            l1.val = carry;
            carry = 0;
        }
        return l1;     
    }
       
    public static int len(ListNode head) {
        int count = 0;
        ListNode node = head;
        while (node != null) {
            node = node.next;
            count++;
        }
        return count;
    }
       
    public static void printLinkedList(ListNode head) {
        ListNode node = head;
        while (node != null) {
            if (node.next == null) {
                System.out.print(node.val);
            } else {
                System.out.print(node.val + "->");
            }                  
            node = node.next;
        }
        System.out.println();
    }
}