class ListNode{

    int val;

    ListNode next;

    ListNode(int x){

        val = x;

    }

}
//在使用之前ListNode得next变量前需要进行初始化：
ListNode node = new ListNode(1);
a = node.next;
a = new ListNode(2);
//上面是不能通过node找到刚刚初始化的a, 只有通过下面这种方式才能找到next，形成一条链
node.next = new ListNode(3);
a = node.next; //此时对a操作才能，才能形成对一条链的操作

public class Solution {

    public static void main(String[] args) {

        int[] data1 = new int[] {1};

        int[] data2 = new int[] {9,9};

        ListNode node1 = new ListNode(data1[0]);

        ListNode node2 = new ListNode(data2[0]);

        ListNode tmp = node1;

        for(int i = 1; i < data1.length; i ++) {

            tmp.next = new ListNode(data1[i]);

            tmp = tmp.next;

        }

        tmp = node2;

        for(int i = 1; i < data2.length; i ++) {

            tmp.next = new ListNode(data2[i]);

            tmp = tmp.next;

        }

        Solution s = new Solution();

        tmp = s.addTwoNumbers(node1, node2);

        while(tmp != null) {

            System.out.format("%d ", tmp.val);

            tmp = tmp.next;

        }

    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        ListNode head = new ListNode(0);

        ListNode cur_node = head;

        int carry = 0;

        while(l1 != null || l2 != null) {

            int x = (l1 == null) ? 0 : l1.val;

            int y = (l2 == null) ? 0 : l2.val;

            int val = x + y + carry;

            carry = val / 10;

            cur_node.next = new ListNode(val % 10);

            cur_node = cur_node.next;

            if(l1 != null)

                l1 = l1.next;

            if(l2 != null)

                l2 = l2.next;

        }

        if(carry > 0) {

            cur_node.next = new ListNode(1);

        }

        return head.next;

    }

    private class HelpMergeReturn{

        int flag;

        ListNode node;

        HelpMergeReturn(int f, ListNode n){

            flag = f;

            node = n;

        }

    }

    private HelpMergeReturn helpMerge(ListNode node, ListNode l, int flag) {

        while(l != null) {

            int val = l.val + flag;

            flag = val / 10;

            node.next = new ListNode(val % 10);

            node = node.next;

            l = l.next;

        }

        return new HelpMergeReturn(flag, node);

    }

    public ListNode addTwoNumbers1(ListNode l1, ListNode l2) {

        int flag = 0;

        ListNode result = null;

        ListNode tmp_node = null;

        while(true) {

            if(l1 == null || l2 == null)

                break;

            int val = l1.val + l2.val + flag;

            flag = val / 10;

            if(tmp_node == null) {

                tmp_node = new ListNode(val % 10);

                result = tmp_node;

            }

            else {

                tmp_node.next = new ListNode(val % 10);

                tmp_node = tmp_node.next;

            }

            l1 = l1.next;

            l2 = l2.next;

        }

        HelpMergeReturn hm = null;

        if(l1 != null) {

            hm = helpMerge(tmp_node, l1, flag);

        }

        if(l2 != null) {

            hm = helpMerge(tmp_node, l2, flag);

        }

        if(hm != null) {

            tmp_node = hm.node;

            flag = hm.flag;

        }

        if(flag != 0) {

            tmp_node.next = new ListNode(flag);

        }

        return result;

    }

}