/**
 * Definition for singly-linked list.
 * public 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 Solution1 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode res = new ListNode();
        // 不用long时由于链表长度可达100会超int 但long依旧超限制
        long n1 = 0;  
        long n2 = 0;
        long stand = 1;
        while(l1 != null){
            long tmp = l1.val * stand;
            n1 += tmp;
            stand *= 10;
            l1 = l1.next;
        }

        stand = 1;
        while(l2 != null){
            long tmp = l2.val * stand;
            n2 += tmp;
            stand *= 10;
            l2 = l2.next;
        }

        long n = n1 + n2;
        if(n == 0){
            res.val = 0;
            return res;
        }
        ListNode head = res;
        while(n > 0){
            int tt = (int)(n % 10);
            ListNode tmp = new ListNode(tt);
            head.next = tmp;
            head = head.next;
            n /= 10;
        }

        return res.next;
    }
}


// 最优解 直接在链表上模拟十进制运算进行加法及进位操作 
// 难点在于模拟过程需要对进位进行合理处理
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 保存最终链表头部的指针
        ListNode res = new ListNode();
        // 用于帮助构建res的遍历指针
        ListNode head = res;
        // 暂存器 用于l1和l2后面均为null时若前一节点有需要进位的1时则置为一 无该情况默认0
        int extra = 0;
        // 标志位 用于标志哪一个链表在退出第一个while后还有多余未遍历的节点
        boolean f1 = false;
        boolean f2 = false;
        // 采用双指针统一遍历 模拟十进制加法 遇到进位需额外处理 直到某一链表遍历完全或均遍历完全则退出模拟
        while(l1 != null && l2 != null){
            int n1 = l1.val;
            int n2 = l2.val;
            int n = n1 + n2;
            // 发生进位
            if(n >= 10){
                int tmp = n % 10;
                // 及时进1给高位 若l1后不空可进位到l1下一点 若空进到l2下一点
                // 若后面均空则进位到暂存器extra
                if(l1.next != null)
                    l1.next.val++;
                else if(l2.next != null)
                    l2.next.val++;
                else    
                    extra = 1;
                ListNode tNode = new ListNode(tmp);
                head.next = tNode;
            }
            // 未进位 直接新增和的节点
            else{
                ListNode tNode = new ListNode(n);
                head.next = tNode;
            }
            // head记得要移动
            head = head.next;

            // 越界判断 方便while模拟加法过程退出后哪一链表会剩余节点
            if(l1.next == null && l2.next == null){
                f1 = true;
                f2 = true;
            }
            else if(l1.next == null){
                f1 = true;
            }
            else if(l2.next == null){
                f2 = true;
            }

            // 固定移动
            l1 = l1.next;
            l2 = l2.next;
        }
        // 不可直接将余下的直接链接 因可能存在低位向不为null的节点高位+1情况 会导致9->10 故要检查
        // eg： l1 = [9,9,9,9,9,9,9] l2 = [9,9,9,9] 
        // 不加额外操作输出 [8,9,9,9,10,9,9]
        // 正确为 [8,9,9,9,0,0,0,1]
        if(f1 && !f2){
            if(l2.val == 10){
                // 标志位 标志l2余下链表是否有东西
                boolean flag = false;
                // 若出现上述预测情况 则要进行循环判断 因可能后1进到前1导致前由9->10 故要继续进位
                while(l2.val == 10){
                    ListNode tNode = new ListNode(0);
                    head.next = tNode;
                    head = head.next;
                    // 后有东西直接进位+1
                    if(l2.next != null){
                        l2 = l2.next;
                        l2.val++;
                    }
                    // 后无东西则创建一新节点即可 同时l2代表遍历完全
                    else{
                        ListNode tmpNode = new ListNode(1);
                        head.next = tmpNode;
                        flag = true;
                        break;
                    }
                }
                // 直至余下链表中无10 此时可直接链接
                if(!flag)
                    head.next = l2;
            }

            // 无10 可直接链接
            else{
                head.next = l2;
            }
        }
        // 同上
        else if(!f1 && f2){
            if(l1.val == 10){
                // 标志位 标志余下链表是否有东西
                boolean flag = false;
                // 若出现上述预测情况 则要进行循环判断 因可能后1进到前1导致前由9->10 故要继续进位
                while(l1.val == 10){
                    ListNode tNode = new ListNode(0);
                    head.next = tNode;
                    head = head.next;
                    // 后有东西直接进位+1
                    if(l1.next != null){
                        l1 = l1.next;
                        l1.val++;
                    }
                    // 后无东西则创建一新节点即可 同时l1代表遍历完全
                    else{
                        ListNode tmpNode = new ListNode(1);
                        head.next = tmpNode;
                        flag = true;
                        break;
                    }
                }
                // 直至余下链表中无10 此时可直接链接
                if(!flag)
                    head.next = l1;
            }

            // 无10 可直接链接
            else{
                head.next = l1;
            }
        }

        // 此不存在上述情况 但可能存在extra 故要考虑是否要因进位而多增加一个节点 其val=1
        else if(f1 && f2){
            if(extra == 1){
                ListNode tNode = new ListNode(1);
                head.next = tNode;
            }
        }

        // res为带头节点的链表 故返回其next
        return res.next;
    }
}