LeetCode 2 | Add Two Numbers 两数相加

[hughie8]

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
};

运行效果

Comments

[steemexplorers]

You have been upvoted by all four members of the @steemexplorers team. Steemexplorers is an initiative to help bring all Steemians information on various services and communities operating all on the STEEM blockchain in a centralized location to save you time and help you grow here on Steemit. It's free, it's easy, and there's a whole lot of information here that you can put to good use. Please come by our discord channel to learn more and feel free to ask as many questions as you'd like. We're here to help! Link to Discord: https://discord.gg/6QrMCFq

[drotto]

This post has received a 3.13 % upvote from @drotto thanks to: @hughie8.