【leetcode】2. 两数相加

栏目: 数据库 · 发布时间: 5年前

内容简介:给出两个如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外,这两个数都不会以 0 开头。

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

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

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

示例:

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

实现思路:

典型的链表遍历操作题,非常简单的指针操作,做题时注意考虑到边界条件判断即可。

  1. 实例化结果链表 result
  2. 创建 3 个 Node 变量(代替指针)指向 被加数链表 的第二个节点(因为头节点在实例化 result 时已经操作过)以及 result 链表 的头节点;
  3. 循环链表直至最长的链表遍历结束以及进制为 0
  4. 在循环内将节点值相加并操作 Node 变量指向下一个节点即可;

注:

  1. 为了加快算法速度,取整时我放弃了 parseInt ,转而使用位运算 ~~
  2. 另一种思路是先创建一个空头节点作为 result 链表 的头节点,所有相加的操作都放在循环中,最后返回 result.next 即可。这种方法可以 AC ,但由于多了一个空节点,在内存和性能上都稍差。

我的实现:

/**
 * 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) {
  const count = l1.val + l2.val
  let carry = ~~(count / 10)
  const result = new ListNode(count % 10)
  let currentNode1 = l1.next
  let currentNode2 = l2.next
  let currentNode3 = result
  while (currentNode1 || currentNode2 || carry) {
    let digit = carry
    if (currentNode1 && currentNode2) {
      digit += currentNode2.val + currentNode1.val
      currentNode1 = currentNode1.next
      currentNode2 = currentNode2.next
    } else if (currentNode1) {
      digit += currentNode1.val
      currentNode1 = currentNode1.next
    } else if (currentNode2) {
      digit += currentNode2.val
      currentNode2 = currentNode2.next
    }
    carry = ~~(digit / 10)
    currentNode3 = currentNode3.next = new ListNode(digit % 10)
  }
  return result
};

成绩

【leetcode】2. 两数相加

【leetcode】2. 两数相加


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Effective Java

Effective Java

Joshua Bloch / Addison-Wesley Professional / 2018-1-6 / USD 54.99

The Definitive Guide to Java Platform Best Practices—Updated for Java 9 Java has changed dramatically since the previous edition of Effective Java was published shortly after the release of Jav......一起来看看 《Effective Java》 这本书的介绍吧!

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

SHA 加密
SHA 加密

SHA 加密工具