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

一、题目描述

给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。

请你将两个数相加,并以相同形式返回一个表示和的链表。

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

二、题目解析

三、参考代码

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

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

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

        // l1 和 l2 有可能为空,所以先默认结果链表从虚拟头结点位置开始
        ListNode cur = dummy;

        // 同时遍历 l1 和 l2
        // 只要此时 l1 和 l2 两个链表中的任意链表中节点有值,就一直加下去
        // 直到两个链表中的所有节点都遍历完毕为止
        while(l1 != null || l2 != null) {
            // 获取 l1 链表中节点的值
            int x;

            // 观察此时 l1 中的节点是否有值
            // 如果节点不存在,那么就用 0 来占位
            if( l1 == null){
                // 用 0 来占位
                x = 0;
            }else{
                // 否则,将 l1 的节点值赋值给 x
                x = l1.val;
            }

            // 获取 l2 链表中节点的值
            int y;

            // 观察此时 l2 中的节点是否有值
            // 如果节点不存在,那么就用 0 来占位
            if( l2 == null){
                // 用 0 来占位
                y = 0;
            }else{
                // 否则,将 l2 的节点值赋值给 y
                y = l2.val;
            }

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

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

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

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

            // 把这个节点加入到结果链表中
            cur.next = digitNode;

            // 移动 cur 的位置,观察后面应该存放什么节点
            cur = cur.next;

            // l1 链表中还有节点未遍历完毕就继续遍历下去
            if(l1 != null) l1 = l1.next;

            // l2 链表中还有节点未遍历完毕就继续遍历下去
            if(l2 != null) l2 = l2.next;
        }

        // 两个链表的尾节点相加之后,有可能产生进位的情况
        // 所以,需要构建一个新的节点用来存放这个进位的结果
        if(carryBit == 1) {
            // 构建一个节点用来存放这个进位
            ListNode carryBitNode = new ListNode(carryBit);

            // 把这个节点加入到结果链表中
            cur.next = carryBitNode;
        }

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

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

发表评论

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