算法训练营第一期 | 两数相加 II

一、题目描述

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外,这两个数字都不会以零开头。

二、题目解析

三、参考代码

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        // 构建两个栈,用来储存两个链表中的元素

        // stack1 用来存储链表 l1 中的元素
        Stack<Integer> stack1 = new Stack<Integer>();

        // stack2 用来存储链表 l2 中的元素
        Stack<Integer> stack2 = new Stack<Integer>();

        // 依次把链表 l1 中的元素加入到 stack1 中
        while (l1 != null) {
            // 把当前节点加入到 stack1 中
            stack1.push(l1.val);
            // 继续向后遍历
            l1 = l1.next;
        }

        // 依次把链表 l2 中的元素加入到 stack2 中
        while (l2 != null) {
            // 把当前节点加入到 stack2 中
            stack2.push(l2.val);
            // 继续向后遍历
            l2 = l2.next;
        }

        // 设置一个进位,初始化为 0
        // 两个个位数相加,进位只能是 1 或者 0
        // 比如 7 + 8 = 15,进位是 1
        // 比如 2 + 3 = 6,没有进位,或者说进位是 0
        int carryBit = 0;

        // 构建一个链表用来存放 l1 和 l2 两个链表相加的结果
        // 其中 dummy 这个节点为虚拟头结点
        ListNode dummy = new ListNode(-1);

        // 只要任意一个栈或者 carryBit 有值,那么就需要求和
        while (!stack1.isEmpty() || !stack2.isEmpty() || carryBit != 0) {

            // 三目运算符,如果栈为空,就用 0 来占位,否则使用栈顶元素值

            // 获取 stack1 的栈顶元素值
            int x = stack1.isEmpty() ? 0 : stack1.pop();

            // 获取 stack2 的栈顶元素值
            int y = stack2.isEmpty() ? 0 : stack2.pop();

            // 每一位计算的同时需要考虑上一位的进位情况
            int sum = x + y + carryBit;

            // 获取当前计算结果的十位数
            // 比如 7 + 8 = 15
            // 那么 sum / 10 = 1,进位为 1
            carryBit = sum / 10;

            // 获取当前计算结果的个位数
            // 比如 7 + 8 = 15
            // 那么 sum % 10 = 5
            int diget =  sum % 10;

            // 构建一个节点用来存放这个个位数
            ListNode digetNode = new ListNode(diget);

            // 把这个节点插入到结果链表中
            // 注意是插入,越后面计算的结果越在链表的前面

            // 一开始,dummy 后面没有其它节点,当发生求和计算时
            if(dummy.next == null){
                // 第一个计算结果直接加入到 dummy 后面
                dummy.next = digetNode;
            }else{

                // 新的节点的 next 指针为之前的虚拟头节点 dummy 后面的那个节点
                digetNode.next = dummy.next;

                // 更新 dummy 的 next 指针指向的节点
                dummy.next = digetNode;
            }
        }

        // 最后返回结果链表的头节点就行,即虚拟头结点的下一个节点
        return dummy.next;
    }
}

四、动画理解(没有声音)

发表评论

邮箱地址不会被公开。 必填项已用*标注