import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        //特殊值处理，如果链表1为空，则返回链表2
        if(head1 == null){
            return head2;
        }
        //特殊值处理，如果链表2为空，则返回链表1
        if(head2 == null){
            return head1;
        }
        //调用外部接口，先将链表1和链表2反转
        head1 = ReverseList(head1);
        head2 = ReverseList(head2);
        ListNode head0 = null;  //创建一个新的链表，用来保存两个链表相加后的结果
        ListNode root = head0;
        int count = 0;   //当前两个节点的十进制数
        int count1 = 0;  //前两个节点的十进制数
        int sum = 0;   //两个节点值的和以及前两个节点的十进制数
        ListNode temp = null; //链表新增的节点指针
        while (head1 != null && head2 != null){//当链表1和链表2都不为空时，两个链表对应的节点相加
            count = 0;  //更新当前两个节点的十进制数
            sum = head1.val + head2.val + count1;  //当前两个节点值的和以及前两个节点的十进制数
            if(sum > 9){//当和大于9时，需要进十进制
                count = 1;  //更新当前两个节点的十进制数
                sum = sum%10;  //更新当前两个节点值的和以及前两个节点的十进制数
            }
            temp = new ListNode(sum);  //创建新增的节点
            count1 = count;  //更新前两个节点的十进制数
            if(head0 == null){//如果是头节点，则指向新创建的节点
                head0 = temp;
                root = head0;//保存新创建的链表的头指针，后续需要反转该链表
            }else {//如果不是头节点，则它的后继节点指向新创建的节点,
                head0.next = temp;
                head0 = head0.next;//并且移动当前节点head0，head0保证永远指向链表的尾节点
            }
            head1 = head1.next;//链表1节点移动
            head2 = head2.next;//链表2节点移动
        }
        while (head1 != null){//当链表1不为空时，此时链表2为空，只需要将链表1节点值与前两个节点的十进制数相加即可
            count = 0;  //更新当前两个节点的十进制数
            sum = head1.val+count1;  //链表1节点值与前两个节点的十进制数相加
            if(sum > 9){
                count = 1;
                sum = sum%10;
            }
            temp = new ListNode(sum);
            count1 = count;
            head0.next = temp;
            head0 = head0.next;
            head1 = head1.next;
        }
        while (head2 != null){//当链表2不为空时，此时链表1为空，只需要将链表2节点值与前两个节点的十进制数相加即可
            count = 0;  //更新当前两个节点的十进制数
            sum = head2.val+count1;  //链表2节点值与前两个节点的十进制数相加
            if(sum > 9){
                count = 1;
                sum = sum%10;
            }
            temp = new ListNode(sum);
            count1 = count;
            head0.next = temp;
            head0 = head0.next;
            head2 = head2.next;
        }
        //当链表1和链表2都为空时，如果前两个节点的十进制数大于0，则还需要新创建一个节点，保存十进制数
        if(count1 > 0 ){
            temp = new ListNode(count1);
            head0.next = temp;
            count1 = 0;//将十进制数变为0
        }
        root = ReverseList(root);
        return root;
    }
    
    public static ListNode ReverseList(ListNode head) {
        if(head == null || head.next == null){//特殊值处理，空链表，或者链表的长度为1
            return head;
        }
        ListNode prep = null;  //保存当前节点的前驱节点
        ListNode next = head.next;  //保存当前节点的后继节点
        while (head != null){//遍历链表，head指向当前遍历的链表节点
            next = head.next;  //保存当前节点的后继节点
            head.next = prep;  //实现链表方向反转
            prep = head;  //前驱节点后移
            head = next;  //当前节点后移
        }
        return prep;//返回链表反转后的头指针
    }
}