内容简介:给出两个如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出:7 -> 0 -> 8 原因:342 + 465 = 807
实现思路:
典型的链表遍历操作题,非常简单的指针操作,做题时注意考虑到边界条件判断即可。
- 实例化结果链表
result
; - 创建 3 个
Node
变量(代替指针)指向 被加数链表 的第二个节点(因为头节点在实例化result
时已经操作过)以及result
链表 的头节点; - 循环链表直至最长的链表遍历结束以及进制为
0
; - 在循环内将节点值相加并操作
Node
变量指向下一个节点即可;
注:
- 为了加快算法速度,取整时我放弃了
parseInt
,转而使用位运算~~
- 另一种思路是先创建一个空头节点作为
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 };
成绩
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。