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

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) {
        // write code here
        ListNode p1 = head1;
        ListNode p2 = head2;

        // Reverse LinkedList
        LinkedList<Integer> stack1 = new LinkedList();
        LinkedList<Integer> stack2 = new LinkedList();

        while (p1 != null) {
            stack1.push(p1.val);
            p1 = p1.next;
        }
        while (p2 != null) {
            stack2.push(p2.val);
            p2 = p2.next;
        }

        // sum, pre_mark, tail_result_node
        int sum = 0, carray = 0;
        ListNode sumHead = null; 

        // 加上 carray != 0 条件是因为：高位相加有可能需要向更高位进 1
        while (!stack1.isEmpty() || !stack2.isEmpty() || carray != 0) {
            sum = 0;
            if (!stack1.isEmpty()) {
                sum += stack1.pop();
            }
            if (!stack2.isEmpty()) {
                sum += stack2.pop();
            }
            sum += carray;

            // 总数分解
            carray = sum / 10;
            sum = sum % 10;

            // 结果链表节点重连
            ListNode curNode = new ListNode(sum);
            curNode.next = sumHead;
            sumHead = curNode;
        }
        return sumHead;
    }
}

懒得手写了，直接Copy一个改了一下。

思路：Stack（链表反转）

个人看法：可以将内部判断移到外面，也就是两个栈累计和到任一栈为空。其次是将不为空的栈循环遍历。