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

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        //加数1
        Stack<ListNode> stack1 = new Stack<>();
        //加数2
        Stack<ListNode> stack2 = new Stack<>();
        //结果
        Stack<ListNode> result = new Stack<>();

        //将数1和数2入栈
        while (head1 != null) {
            stack1.push(head1);
            head1 = head1.next;
        }

        while (head2 != null) {
            stack2.push(head2);
            head2 = head2.next;
        }

        //循环两个栈内的值，相加，并记录是否进1
        int upToNext = 0;
        while (!stack1.isEmpty() || !stack2.isEmpty()) {
            int firstNum = 0;
            int secondNum = 0;
            if (!stack1.isEmpty()) {
                firstNum = stack1.pop().val;
            }
            if (!stack2.isEmpty()) {
                secondNum = stack2.pop().val;
            }
            int plusNum = firstNum + secondNum + upToNext;

            if (plusNum >= 10) {
                upToNext = 1;
                plusNum = plusNum - 10;
            } else {
                upToNext = 0;
            }
            ListNode node = new ListNode(plusNum);
            result.push(node);
        }

        //最后留下了进位数，需要再加一个结点，入栈
        if (upToNext > 0) {
            result.push(new ListNode(upToNext));
        }

        return stackToNode(result);
    }

    //将栈内数据出栈，形成链表
    public ListNode stackToNode(Stack<ListNode> stack) {
        ListNode resultNode = null;
        ListNode curNode = null;
        while (!stack.isEmpty()) {
            if (resultNode == null) {
                resultNode = stack.pop();
                curNode = resultNode;
            } else {
                curNode.next = stack.pop();
                curNode = curNode.next;
            }
        }
        return resultNode;
    }


}