题解 | #两个链表生成相加链表#

三个栈 完美解决，JAVA YYDS

import java.util.*;
public class Solution {
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
     //保存head1的值
    Stack<Integer> stack1 = new Stack<>();
     //保存head2的值
    Stack<Integer> stack2 = new Stack<>();
    //保存计算结果的值
    Stack<Integer> stack3 = new Stack<>();
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        while(head1!=null){
            stack1.push(head1.val);
            head1 = head1.next;
        }   
        //stack1 = {9 3 7};
         while(head2!=null){
            stack2.push(head2.val);
            head2 = head2.next;
        }
       //stack2 = {6,3};
       //记录进位
        int prv = 0;
        while(!stack1.isEmpty() || !stack2.isEmpty()){
             //如果栈1为空
             if(stack1.isEmpty()){
                 //弹出栈2的顶部 + 进位值
                 int p2 = stack2.pop();
                if(p2 + prv >= 10){
                   //大于10 和 减去 10 压入栈3 同时需进一位
                    stack3.push((p2 + prv) - 10);  
                    //进位值设为1
                    prv = 1;
                }else{
                     stack3.push(p2 + prv); 
                    prv = 0;
                }
                 continue;
            }
            //同上面
             if(stack2.isEmpty()){
                int p2 = stack1.pop();
                if(p2 + prv >= 10){
                    stack3.push((p2 + prv) - 10);  
                    prv = 1;
                }else{
                     stack3.push(p2 + prv); 
                    prv = 0;
                }
                 continue;
            }
           //如果都不为空 ，同时取出来栈顶 如 7 跟 3
            if(!stack1.isEmpty() && !stack2.isEmpty()){
                int p1 = stack1.pop();
                int p2 = stack2.pop();
                // 7 +3 + 0 > =10
                if(p1 + p2 + prv >= 10){
                    stack3.push((p1 + p2 + prv) - 10);  
                    prv = 1;
                }else{
                 //如果加上进位值都小于10 进位值已被使用 初始化为0
                     stack3.push(p1 + p2 + prv); 
                     prv = 0;
                }
            }
        }
        //两个栈都弹完了 判断进位还有没有 有就直接压入栈3顶 
        if(prv == 1) stack3.push(prv);
        //栈3 的顺序 0 0 0 1
        //构建链表
        ListNode node = new ListNode(0);
        ListNode cru = node;
        while(!stack3.isEmpty()){
            int val = stack3.pop();
            cru.next = new ListNode(val);
            cru = cru.next; 
        } 
      return node.next;
    }
}