class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }
    ListNode(int val) {
        this.val = val;
    }
    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

class Solution_Loop {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode result = new ListNode();
        ListNode resultNext = null;
        boolean needAdd = false;
        int sum;
        while (l1 != null || l2 != null) {
            // 对 result 的扩展需要在下一轮的循环初始判断，如果能进入下一轮循环说明 result 还需要新增节点，
            // 否则在尾部扩展可能下一轮循环不满足条件退出，导致 result 多出一个 0 节点（默认值）。
            if (resultNext == null) {
                // resultNext == null 说明是第一次进入循环，则 next 就等于头节点。
                resultNext = result;
            } else {
                // resultNext != null 说明进入新一轮循环，说明还有节点需要求和，
                // 则令创建一个新的 result 节点并拼接到 result 链表的尾部。
                resultNext.next = new ListNode();
                resultNext = resultNext.next;
            }
            // 如果任意一条链表已经结束，则按 0 取值。
            sum = getVal(l1) + getVal(l2);
            // 上一轮循环是否需要进位，如果需要则 + 1
            if (needAdd) {
                sum++;
            }
            // 对当前位的节点求和并加了进位后，再判断是否大于等于 10，是则继续进位。
            if (sum > 9) {
                sum %= 10;
                needAdd = true;
            } else {
                needAdd = false;
            }
            resultNext.val = sum;
            // 为下一轮循环准备需要求和的节点。
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        // 循环结束后，还需要对是否有最后一个进位做判断，
        // 因此需要确保最后进位的是链表最末端的 next 节点，
        // 但有可能没有进循环导致 resultNext 为空，所以需要多一层判断。
        if (resultNext == null) {
            resultNext = result;
        }
        if (needAdd) {
            resultNext.next = new ListNode(1);
        }
        return result;
    }

    private int getVal(ListNode node) {
        return (node == null) ? 0 : node.val;
    }
}

class Solution_Recursion {
    // 记录是否需要进位
    private boolean needAdd = false;
    /**
      * 使用递归的方式，将该方法的返回值作为结果链表的「next」节点。
      */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 如果两个链表均便利完成，且没有进位，说明运算结束，也即「next」为 null。
        if (l1 == null && l2 == null && !needAdd) {
            return null;
        }
        // 计算 l1 和 l2 当前节点的和（以及前一项是否有进位）
        int sum = getVal(l1) + getVal(l2) + (needAdd ? 1 : 0);
        // sum 除以 10 大于零表示需要进位
        needAdd = (sum / 10) > 0;
        // 记录「next」节点的值，如果是第一个节点，则「next」就表示首个节点。
        ListNode next = new ListNode(sum %= 10);
        // 递归获取「next.next」节点
        next.next = addTwoNumbers((l1 == null ? null : l1.next), (l2 == null ? null : l2.next));
        // 所有节点的「next」节点都递归获取后，返回首节点。
        // 由于递归时声明的 next 是在方法体内的，所以最终返回的 next 是最外层的 next，即首节点。
        return next;
    }

    private int getVal(ListNode node) {
        return (node == null) ? 0 : node.val;
    }
}