445. Add Two Numbers II
Вам даны два непустых связанных списка, представляющих два неотрицательных целых числа. Самый значимый разряд стоит первым, и каждый из их узлов содержит одну цифру. Сложите два числа и верните сумму в виде связанного списка.
Вы можете предположить, что оба числа не содержат начальных нулей, за исключением самого числа 0.
Пример:
Input: l1 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]
C# решение
сопоставлено/оригиналpublic class ListNode {
public int val;
public ListNode next;
public ListNode(int val = 0, ListNode next = null) {
this.val = val;
this.next = next;
}
}
public class Solution {
private ListNode ReverseList(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode temp = head.next;
head.next = prev;
prev = head;
head = temp;
}
return prev;
}
public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
ListNode r1 = ReverseList(l1);
ListNode r2 = ReverseList(l2);
int carry = 0;
ListNode ans = null;
while (r1 != null || r2 != null || carry > 0) {
if (r1 != null) {
carry += r1.val;
r1 = r1.next;
}
if (r2 != null) {
carry += r2.val;
r2 = r2.next;
}
ListNode newNode = new ListNode(carry % 10);
newNode.next = ans;
ans = newNode;
carry /= 10;
}
return ans;
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class ListNode {
public int val;
public ListNode next;
public ListNode(int val = 0, ListNode next = null) {
this.val = val;
this.next = next;
}
}
class Solution {
public:
private ListNode ReverseList(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode temp = head.next;
head.next = prev;
prev = head;
head = temp;
}
return prev;
}
public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
ListNode r1 = ReverseList(l1);
ListNode r2 = ReverseList(l2);
int carry = 0;
ListNode ans = null;
while (r1 != null || r2 != null || carry > 0) {
if (r1 != null) {
carry += r1.val;
r1 = r1.next;
}
if (r2 != null) {
carry += r2.val;
r2 = r2.next;
}
ListNode newNode = new ListNode(carry % 10);
newNode.next = ans;
ans = newNode;
carry /= 10;
}
return ans;
}
}Java решение
сопоставлено/оригиналclass Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode temp = null;
while (head != null) {
temp = head.next;
head.next = prev;
prev = head;
head = temp;
}
return prev;
}
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode r1 = reverseList(l1);
ListNode r2 = reverseList(l2);
int totalSum = 0;
int carry = 0;
ListNode ans = new ListNode();
while (r1 != null || r2 != null) {
if (r1 != null) {
totalSum += r1.val;
r1 = r1.next;
}
if (r2 != null) {
totalSum += r2.val;
r2 = r2.next;
}
ans.val = totalSum % 10;
carry = totalSum / 10;
ListNode head = new ListNode(carry);
head.next = ans;
ans = head;
totalSum = carry;
}
return carry == 0 ? ans.next : ans;
}
}JavaScript решение
сопоставлено/оригиналfunction ListNode(val, next) {
this.val = val === undefined ? 0 : val;
this.next = next === undefined ? null : next;
}
var reverseList = function(head) {
let prev = null;
let temp = null;
while (head !== null) {
temp = head.next;
head.next = prev;
prev = head;
head = temp;
}
return prev;
};
var addTwoNumbers = function(l1, l2) {
let r1 = reverseList(l1);
let r2 = reverseList(l2);
let totalSum = 0;
let carry = 0;
let ans = new ListNode(0);
while (r1 !== null || r2 !== null) {
if (r1 !== null) {
totalSum += r1.val;
r1 = r1.next;
}
if (r2 !== null) {
totalSum += r2.val;
r2 = r2.next;
}
ans.val = totalSum % 10;
carry = Math.floor(totalSum / 10);
let head = new ListNode(carry);
head.next = ans;
ans = head;
totalSum = carry;
}
return carry === 0 ? ans.next : ans;
};Python решение
сопоставлено/оригиналclass Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
prev = None
temp = None
while head:
temp = head.next
head.next = prev
prev = head
head = temp
return prev
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
r1 = self.reverseList(l1)
r2 = self.reverseList(l2)
total_sum = 0
carry = 0
ans = ListNode()
while r1 or r2:
if r1:
total_sum += r1.val
r1 = r1.next
if r2:
total_sum += r2.val
r2 = r2.next
ans.val = total_sum % 10
carry = total_sum // 10
head = ListNode(carry)
head.next = ans
ans = head
total_sum = carry
return ans.next if carry == 0 else ansGo решение
сопоставлено/оригиналtype ListNode struct {
Val int
Next *ListNode
}
func reverseList(head *ListNode) *ListNode {
var prev *ListNode
var temp *ListNode
for head != nil {
temp = head.Next
head.Next = prev
prev = head
head = temp
}
return prev
}
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
r1 := reverseList(l1)
r2 := reverseList(l2)
totalSum := 0
carry := 0
ans := &ListNode{}
for r1 != nil || r2 != nil {
if r1 != nil {
totalSum += r1.Val
r1 = r1.Next
}
if r2 != nil {
totalSum += r2.Val
r2 = r2.Next
}
ans.Val = totalSum % 10
carry = totalSum / 10
head := &ListNode{Val: carry}
head.Next = ans
ans = head
totalSum = carry
}
if carry == 0 {
return ans.Next
}
return ans
}Algorithm
Создайте два связанных списка r1 и r2, чтобы хранить перевернутые связанные списки l1 и l2 соответственно. Создайте два целых числа totalSum и carry для хранения суммы и переноса текущих цифр. Создайте новый ListNode, ans, который будет хранить сумму текущих цифр. Мы будем складывать два числа, используя перевернутый список, добавляя цифры по одной. Продолжаем, пока не пройдем все узлы в r1 и r2.
Если r1 не равен null, добавляем r1.val к totalSum. Если r2 не равен null, добавляем r2.val к totalSum. Устанавливаем ans.val = totalSum % 10. Сохраняем перенос как totalSum / 10. Создаем новый ListNode, newNode, который будет иметь значение как перенос. Устанавливаем next для newNode как ans. Обновляем ans = newNode, чтобы использовать ту же переменную ans для следующей итерации. Обновляем totalSum = carry.
Если carry == 0, это означает, что newNode, созданный в финальной итерации цикла while, имеет значение 0. Поскольку мы выполняем ans = newNode в конце каждой итерации цикла while, чтобы избежать возврата связанного списка с головой, равной 0 (начальный ноль), возвращаем следующий элемент, т.е. возвращаем
ans.next
. В противном случае, если перенос не равен 0, значение ans не равно нулю. Следовательно, просто возвращаем ans.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.