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

两个链表生成相加链表

http://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b

描述

假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
给定两个这种链表，请生成代表两个整数相加值的结果链表。
例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。

示例1

输入：
[9,3,7],[6,3]

返回值：
{1,0,0,0}

思路

这道题要的是将两个链表相加，并且在生成一个新的链表。因为考虑到相加会产生进位问题，所以要从后往前加，这样每次产生的进位值就可以用上。
但是问题来了，链表无法从后往前访问，所以咱们需要借助一个数据结构：“栈”。对于栈想必大家都很熟悉，先进后出的特性正好符合这道题的要求。

先将两个链表分别压入两个栈中。
然后弹出栈顶的两个元素
两个元素相加，如果小于 10，那么这个值就是新节点的值；如果大于 10，余数为新节点的值，进位值存储起来用于下一组节点相加。

AC 代码

public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        if (head1 == null) {
            return head2;
        } else if (head2 == null) {
            return head1;
        }

        Stack<ListNode> stack1 = new Stack<>();
        Stack<ListNode> stack2 = new Stack<>();
        // 将 head1 所有的元素入栈
        while (head1 != null) {
            stack1.push(head1);
            head1 = head1.next;
        }
        // 将 head2 所有的元素入栈
        while (head2 != null) {
            stack2.push(head2);
            head2 = head2.next;
        }
        // 定义哑节点
        ListNode dummyNode = new ListNode(-1);
        // 用于存储每次的进位值
        int carryValue = 0;
        while (!stack1.isEmpty() || !stack2.isEmpty()) {
            // 弹出栈定的元素，如果为空则为0
            int num1 = stack1.isEmpty() ? 0 : stack1.pop().val;
            int num2 = stack2.isEmpty() ? 0 : stack2.pop().val;
            // 本轮数值总和为 两个节点的值 + 上一次进位的值
            int currentTotalValue = num1 + num2 + carryValue;
            // 本轮新节点真实的值为 currentTotalValue 对 10 取余，
            // 因为节点值只能是 10 以下，大于的就需要进位
            int currentRealValue = currentTotalValue % 10;
            // 本轮进位值为 currentTotalValue 除以 10，
            // 这种方法是想拿到进位值，如果没有进位值，那么就为0，也不影响下一次计算
            carryValue = currentTotalValue / 10;
            // 创建本轮的新节点
            ListNode currentNode = new ListNode(currentRealValue);
            // 这步就是想将新的节点插入 dummyNode 之后，其他节点之前
            currentNode.next = dummyNode.next;
            dummyNode.next = currentNode;
        }
        return dummyNode.next;
    }

时间复杂度：O(N)，N两个链表的最长长度
空间复杂度：O(N)，使用栈最为额外存储空间