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

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) {
	  //思想：使用三个栈来分别存储链表1，链表2，链表1+2。通过栈的特性来进行相加
        // write code here
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        Stack<Integer> stack3 = new Stack<>();
	  //将链表1所有节点入栈1
        while (head1 != null) {
            stack1.push(head1.val);
            head1 = head1.next;
        }
	  //将链表2所有节点入栈2
        while (head2 != null) {
            stack2.push(head2.val);
            head2 = head2.next;
        }
        //表示是否进位?0不进位/1进位
        int add = 0;
	  	//栈1或2不为空
        while (!stack1.isEmpty() || !stack2.isEmpty()) {
            //如果栈1为空
            if (stack1.isEmpty()) {
                //有进位则+1再入栈
                if (add == 1) {
                    int num = stack2.pop();
                    num++;
                    add = 0;
				  	//进位后如果大于1-则改变进位状态再入栈
                    if (num >= 10) {
                        add = 1;
                        num -= 10;
                        stack3.push(num);
                    }else{
                        stack3.push(num);
                    }
				  //无进位直接入栈
                }else{
                    int num = stack2.pop();
                	stack3.push(num);
                }
                
                //如果栈2为空
            } else if (stack2.isEmpty()) {
			 	 //有进位则+1再入栈
                if (add == 1) {
                    int num = stack1.pop();
                    num++;
                    add = 0;
				  //进位后如果大于1-则改变进位状态再入栈
                    if (num >= 10) {
                        add = 1;
                        num -= 10;
                        stack3.push(num);
                    }else{
                        stack3.push(num);
                    }
                }else{
                    int num = stack1.pop();
                    stack3.push(num);
                }
                
                //如果栈12都不为空
            } else {
                Integer num1 = stack1.pop();
                Integer num2 = stack2.pop();
                Integer num3 = num1 + num2;
			  	//有进位则两数相加再+1
                if (add == 1) {
                    num3 += 1;
                    add = 0;
                }
                if (num3 >= 10) {
                    add = 1;
                    num3 -= 10;
                    stack3.push(num3);
                }else{
                    stack3.push(num3);
                }
            }
        }
	  	//最终如果有进位则+1
        if(add==1){
            stack3.push(1);
        }
	  //创建链表将内容添加进去
        ListNode tmp=new ListNode(stack3.pop());
        ListNode returnList=tmp;
        while(!stack3.isEmpty()){
            ListNode tmpNode=new ListNode(stack3.pop());
            tmp.next=tmpNode;
            tmp=tmp.next;
        }
        return returnList;
    }
}