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

因为是从后相加，往前进位，使用栈最方便，每次各取一个数，相加，分别与10取余和取模，余数作为进位，模作为值。由于下一个和需要加上进位，所以每次各取一个数相加时还需要加上余数。模就是最终的节点，所以没得到一个模，就将其插入到head后面，head后面原来的值后移，由于栈空之后还可能进位，所以最后要根据是否进位判断是否还要再插入进位值到head后面。

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) {
        Stack<ListNode> s1 = new Stack<>();
        Stack<ListNode> s2 = new Stack<>();
        
        ListNode c1 = head1;
        ListNode c2 = head2;
        ListNode head=new ListNode(-1);
        while(c1 != null){s1.push(c1);c1 = c1.next;}
        while(c2 != null){s2.push(c2);c2 = c2.next;}
        
        int result = 0;
        while(!s1.empty() || !s2.empty()){
            int a=0,b=0;
            if(!s1.empty())a=s1.pop().val;
            if(!s2.empty())b=s2.pop().val;
            int sum = a+b+result;
            result = sum/10;
            int val = sum%10;
            ListNode cur = new ListNode(val);
            ListNode temp = head.next;
            head.next = cur;
            head.next.next = temp;
           
        }
        
        if(result == 1){
            ListNode temp = head.next;
            ListNode cur = new ListNode(1);
            head.next = cur;
            head.next.next = temp;
        }
        return head.next;
    }
}