2. 两数相加

LeetCode

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

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

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

分析

• 观察题目可能会思考，如何实现进位，和从低位开始依次相加？
• 进位可以通过一个变量来控制
• 按位相加其实就是从链表的根节点依次相加，因为l1,l2两个链表表示的数字是从地位到高位。

基于以上分析何以做一个简单的实现

简单实现

 var addTwoNumbers = function (l1, l2) {
    //新链表
    var head = {
        next: null
    }
    //头指针
    var cur = head;
    //当前为的和
    var sum = 0;
    //进位
    var curry = 0;
    while (l1 !== null || l2 !== null) {
        if (l1 && l2) {
            sum = (l1.sum + l2.sum + curry) % 10;
            curry = (l1.sum + l2.sum + curry) / 10 | 0;
            l1 = l1.next;
            l2 = l2.next;
        }
        if (l1 && !l2) {
            sum = l1.sum
            l1 = l1.next;
        }
        if (!l1 && l2) {
            sum = l2.sum
            l2 = l2.next;
        }
        cur.next = {
            sum: sum,
            next: null
        }
        cur = cur.next;
    }
    return head.next
};

处理边界

虽然上面的代码可以正确输出 7 -> 0 -> 8 的新链表，但是存在很多问题

• 有一个链表为空时没有判断
  如果l1===null 应该直接返回 l2 无需关新 l2 是否为空

• 边界判断
  如果是 [5],[5] 这样的两个链表求和时，没有在while中判断carry是否为有值，不应该直接跳出循环。

• 边界判断
  如果是 [1],[999] 这样的两个链表求和时,即使[1].next===null, 也需要每次循环判断是否需要进位

var addTwoNumbers = function (l1, l2) {
    // 判断边界条件
    if (l1 === null) return l2;
    if (l2 === null) return l1;
    var head = {
        next: null
    }
    var cur = head;
    var sum = 0;
    var carry = 0;
    //有进位是需要继续处理
    while (l1 !== null || l2 !== null || carry) {
        if (l1 && l2) {
            sum = (l1.sum + l2.sum + carry) % 10;
            carry = (l1.sum + l2.sum + carry) / 10 | 0;
            l1 = l1.next;
            l2 = l2.next;
        } else {
            if (!l1 && !l2) {
                sum = carry;
                carry = 0;
            }
            // 处理[999]+[1] 的情况，即使另一个链表为空，也需要注意是否回合当链表的值，产生进位的情况
            if (l1 && !l2) {
                sum = (l1.sum + carry) % 10;
                //位运算取强制转换位整数 等同于Math.floor()
                carry = (l1.sum + carry) / 10 | 0;
                l1 = l1.next;
            }
            if (!l1 && l2) {
                sum = (l2.sum + carry) % 10;
                carry = (l2.sum + carry) / 10 | 0;
                l2 = l2.next;
            }
        }
        cur.next = {
            sum: sum,
            next: null
        }
        cur = cur.next;
    }
    return head.next
};

优化算法

• 清除重复计算,有大量重复的求和与求进位的运算

  sum = (l2.sum + carry) % 10;
  carry = (l2.sum + carry) / 10 | 0;

• 相似的条件语句，我们分别判断 l1 && !l2 和 !l1 && l2 等情况，其实只需要关心，是否l1 !== null || l2 !== null, 如果其中一个链表先位null，它的值可以用0来代替，从而避免大量重复计算

• 经过上面一条的优化，边界条件carry,只需要在循环结束时判断一次即可

var addTwoNumbers = function (l1, l2) {
    var head = {
            next: null
        },
        cur = head,
        carry = 0;
    while (l1 !== null || l2 !== null) {
        var x = l1 !== null ? l1.val : 0,
            y = l2 !== null ? l2.val : 0,
            sum = x + y + carry;
        carry = sum / 10 | 0;
        cur.next = {
            val: sum % 10,
            next: null
        }
        cur = cur.next;
        l1 = l1 !== null ? l1.next : l1
        l2 = l2 !== null ? l2.next : l2
    }
    if (carry > 0) {
        cur.next = {
            val: carry,
            next: null
        }
    }
    return head.next
};

复杂度分析

• 时间复杂度： ，假设 和 分别表示 和 的长度，上面的算法最多重复 次。

• 空间复杂度：。使用的额外空间复杂度为常数。

打赏