题解 | #链表相加(二)#

解题思路：

1.由于两个链表相加是从最后节点开始，链表又不能逆序，那么就翻转链表进行对应节点进行相加，得到一个新的节点

2.新节点数值范围在[0,18],此时遍历新链表，进行进位操作

3.遍历完之后可能存在最后一个节点有进位的可能，判断，如有则新建节点链接到后面

4.翻转链表

public  ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        if(head1==null || head2==null){
            return head2==null?head1:head2;
        }
        //翻转两个链表
        head1=ReverseList(head1);
        head2=ReverseList(head2);
        ListNode cur1=head1;
        ListNode cur2=head2;
        ListNode addPre=null;
        //对应位置的节点相加，和值由链表1承载
        while (cur1 !=null && cur2 !=null){
            cur1.val=cur1.val + cur2.val;
            addPre=cur1;
            cur1=cur1.next;
            cur2=cur2.next;
        }
        //如果是链表1长度更长，不用处理，如果链表2长度更长，则把后续节点拼接到链表1后面
        while (cur2 != null){
            addPre.next=cur2;
            addPre=cur2;
            cur2=cur2.next;
        }
        //对数值进行进十处理
        ListNode resultCur=head1;
        int quotient=0;
        ListNode pre=null;
        while (resultCur != null){
             int val = resultCur.val+quotient;
            if(val>=10){
                quotient = val / 10;
                resultCur.val= val % 10;
            }else {
                resultCur.val=val;
                quotient=0;
            }
            pre=resultCur;
            resultCur=resultCur.next;
        }
        //如果最后还有进数，则新建节点拼接在链表上
        if(quotient>0){
            pre.next=new ListNode(quotient);
        }
        //翻转链表
        head1 = ReverseList(head1);
        return head1;
    }

  public   ListNode ReverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode cur_next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = cur_next;
        }
        return pre;


    }