LeetCode 2 | Add Two Sum 两数相加

题目描述

[Source: (https://leetcode.com/problems/add-two-numbers/)]

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。
如果将这两个数相加起来，则会返回一个新的链表来表示它们的和。假设除了数字 0 之外，这两个数都不会以 0 开头。

分析

如图可知

[Source: https://leetcode.com/problems/add-two-numbers/Figures/2_add_two_numbers.svg]

这是用链表模拟加法的过程，l1链表和l2链表分别表示相加的两个数，每一位相当于链表的一个节点, 用next指针指向下一位，目标就是逐个节点的计算数值, 将计算好的新节点添加到结果链表中

创建一个新的空链表用来盛放结果， 在l1和l2中遍历每一个位置， 用一个变量carry， 记录在每一位上是否进位， 如果l1和l2相同位置的数字相加sum大于10， 则创建一个新的节点,节点的值为 sum对10取余；如果不进位，节点的值即为sum。完成后让根节点指向这个新节点， l1和l2指向下一个节点，重复以上工作

具体步骤：

• 初始化根节点， 初始化当前节点指向根节点， 初始化进位值为 0 （不进位）
• 将p和q分别初始化为链表 l1和 l2 的头部
• 遍历链表l1 和 l2和进位carry ， 直到它们的尾端
  • 将x设为节点p的值, 如果p到达l1的末尾，则将其值设置为0
  • 将y设为节点q的值, 如果q到达l2的末尾，则将其值设置为0
  • 设定节点的相加和 sum = x + y + carry
  • 更新当前节点的进位值，carry = sum / 10 , 取整
  • 创建一个数值为 sum 对 10取余 的新节点，并将其设置为当前结点的下一个节点，然后将当前节点前进到下一个节点
  • 同时，将 p 和 q前进到下一个结点

Javascript 代码

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */

// 时间复杂度 O(Max(m, n))  m, n分别是链表l1, l2中的元素个数
// 空间复杂度 O(Max(m, n))
var addTwoNumbers = function(l1, l2) {
    // 是否进位
    let carry = 0

    // 初始化新链表 盛放结果
    let root = new ListNode(null)
    
    // 当前指针指向结果链表的头部
    let cur = root

    // 当前节点 l1和l2的和 只保留个位， 如果超过 10， carry置为1
    let sum = 0

    // 初始化当前在l1, l2上操作的位置为头部
    let p = l1, q = l2

    // 当p, q没有指向l1, l2的结尾， 或者尚有进位时，给结果链表添加新节点
    while(p != null || q != null || carry) {
        // 取l1, l2当前位置的数值 没有则为0
        let x = p ? p.val : 0
        let y = q ? q.val : 0

        // 当前位置n的和为 l1在n位置的值 + l2在n位置的值 + 进位
        sum = x + y + carry

        // 更新进位
        carry = parseInt(sum / 10)

        // 如果进位了，sum对10取余
        if (carry === 1) {
            sum %= 10
        }

        // 新增一个节点，值为sum
        let node = new ListNode(sum)

        // 结果链表的当前指针指向node, 结果链表往后走一个节点
        cur.next = node
        cur =  cur.next

        // l1和l2链表往后走一个节点
        p = p ? p.next : p
        q = q ? q.next : q
    }
    return root.next
};

运行效果

另外一种更便于理解的写法如下

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    let root = new ListNode(null)
    let cur = root
    let carry = 0
    while(l1 || l2 || carry) {
        let sum = carry
        if (l1) {
            sum += l1.val
            l1 = l1.next
        }
        if (l2) {
            sum += l2.val
            l2 = l2.next
        }
    
        if (sum > 9) {
            carry = 1
            sum %= 10
        } else {
            carry = 0
        }
        
        let node = new ListNode(sum)
        cur.next = node
        cur = cur.next
    }
    return root.next
};

运行效果