2.两数相加
链接:2.两数相加
难度:Medium
标签:递归、链表、数学
简介:给出两个非空的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
题解 1 - javascript
- 编辑时间:2019-09-20
- 执行用时:144ms
- 内存消耗:38.4MB
- 编程语言:javascript
- 解法介绍:创建第三个链表,其中每个值为前两个链表相加,然后再次循环判断是否有一个节点值大于等于 10,若存在则-10 且下一个节点值+1。
var addTwoNumbers = function (l1, l2) {
let node1 = l1,
node2 = l2;
let tempNode = new ListNode(node1.val + node2.val);
let node3 = tempNode;
while (node1.next !== null && node2.next !== null) {
node1 = node1.next;
node2 = node2.next;
tempNode.next = new ListNode(node1.val + node2.val);
tempNode = tempNode.next;
}
if (node1.next !== null) {
tempNode.next = node1.next;
}
if (node2.next !== null) {
tempNode.next = node2.next;
}
tempNode = node3;
while (tempNode !== null) {
if (tempNode.val >= 10) {
tempNode.val -= 10;
if (tempNode.next !== null) {
tempNode.next.val += 1;
} else {
tempNode.next = new ListNode(1);
}
}
tempNode = tempNode.next;
}
return node3;
};
题解 2 - javascript
- 编辑时间:2019-09-20
- 执行用时:248ms
- 内存消耗:46.2MB
- 编程语言:javascript
- 解法介绍:创建待返回链表 node3,创建进位参数 carry,遍历 l1 和 l2,如果节点 1+节点 2+carry 没有大于 10 则直接储存,若相加大于 10 则存入 carry,余数部分直接储存。
var addTwoNumbers = function (l1, l2) {
let tempNode = new ListNode(0);
let node3 = tempNode;
let carry = 0;
while (l1 !== null || l2 !== null) {
let x = l1 === null ? 0 : l1.val;
let y = l2 === null ? 0 : l2.val;
let sum = x + y + carry;
carry = Math.floor(sum / 10);
sum = Math.floor(sum % 10);
console.log(carry, sum);
tempNode.next = new ListNode(sum);
tempNode = tempNode.next;
if (l1 !== null) {
l1 = l1.next;
}
if (l2 !== null) {
l2 = l2.next;
}
}
if (carry === 1) {
tempNode.next = new ListNode(1);
}
return node3.next;
};
题解 3 - typescript
- 编辑时间:2020-10-04
- 执行用时:144ms
- 内存消耗:43.6MB
- 编程语言:typescript
- 解法介绍:遍历所有节点。
function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
const list = new ListNode(0);
let temp = list;
let add = 0;
while (l1 !== null || l2 !== null) {
let sum = (l1?.val ?? 0) + (l2?.val ?? 0) + add;
add = 0;
if (sum >= 10) {
sum -= 10;
add++;
}
temp.next = new ListNode(sum);
temp = temp.next;
l1 = l1 === null ? null : l1.next;
l2 = l2 === null ? null : l2.next;
}
if (add !== 0) temp.next = new ListNode(add);
return list.next;
}
题解 4 - cpp
- 编辑时间:2023-07-02
- 执行用时:20ms
- 内存消耗:69.8MB
- 编程语言:cpp
- 解法介绍:遍历。
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *head = new ListNode(), *p = head;
int add = 0;
while (l1 || l2) {
int val = (l1 ? l1->val : 0) +
(l2 ? l2->val : 0) +
add;
if (val >= 10) val -= 10, add = 1;
else add = 0;
p->next = new ListNode(val);
p = p->next;
if (l1) l1 = l1->next;
if (l2) l2 = l2->next;
}
if (add) p->next = new ListNode(1);
return head->next;
}
};
题解 5 - python
- 编辑时间:2023-07-02
- 执行用时:68ms
- 内存消耗:16.2MB
- 编程语言:python
- 解法介绍:同上。
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
head = ListNode()
p = head
add = 0
while l1 or l2:
val = (l1.val if l1 else 0) + (l2.val if l2 else 0) + add
if val >= 10:
val -= 10
add = 1
else:
add = 0
p.next = ListNode(val)
p = p.next
if l1:
l1 = l1.next
if l2:
l2 = l2.next
if add:
p.next = ListNode(1)
return head.next
题解 6 - rust
- 编辑时间:2023-07-02
- 内存消耗:2MB
- 编程语言:rust
- 解法介绍:同上。
impl Solution {
pub fn add_two_numbers(
mut l1: Option<Box<ListNode>>,
mut l2: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
let mut head = Box::new(ListNode::new(0));
let mut p = &mut head;
let mut p1 = &mut l1;
let mut p2 = &mut l2;
let mut add = 0;
while p1.is_some() || p2.is_some() {
let mut val = match p1 {
Some(ref mut node) => {
p1 = &mut node.next;
node.val
}
None => 0,
} + match p2 {
Some(ref mut node) => {
p2 = &mut node.next;
node.val
}
None => 0,
} + add;
if val >= 10 {
val -= 10;
add = 1;
} else {
add = 0;
}
p.next = Some(Box::new(ListNode::new(val)));
p = p.next.as_mut().unwrap();
}
if add != 0 {
p.next = Some(Box::new(ListNode::new(1)));
}
head.next
}
}