LeetCode Solution, Medium, 2. Add Two Numbers
Published
2. 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 1:
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
Example 2:
Input: l1 = [0], l2 = [0]
Output: [0]
Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
Constraints:
- The number of nodes in each linked list is in the range
[1, 100]. 0 <= Node.val <= 9- It is guaranteed that the list represents a number that does not have leading zeros.
題目翻譯
給兩個資料結構為 Linked List 的參數 l1 和 l2，每個節點都只會有一個位數的值。要將兩個 list 相加。
解法解析
解題方式是最開始的個位數都是在最前面，所以其實很方便的就是從頭去開始遍歷來計算。當超過 10 就記住商數到參數 carry 帶到下個節點。
解法範例
Go
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
head := &ListNode{Val: 0}
n1, n2, carry, current := 0, 0, 0, head
for l1 != nil || l2 != nil || carry != 0 {
if l1 == nil {
n1 = 0
} else {
n1 = l1.Val
l1 = l1.Next
}
if l2 == nil {
n2 = 0
} else {
n2 = l2.Val
l2 = l2.Next
}
current.Next = &ListNode{Val: (n1 + n2 + carry) % 10}
current = current.Next
carry = (n1 + n2 + carry) / 10
}
return head.Next
}
JavaScript
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function (l1, l2) {
const head = new ListNode(0);
let p = l1,
q = l2,
curr = head,
carry = 0;
while (p || q || carry) {
const x = p ? p.val : 0;
const y = q ? q.val : 0;
const sum = x + y + carry;
carry = Math.floor(sum / 10);
curr.next = new ListNode(sum % 10);
curr = curr.next;
p = p ? p.next : null;
q = q ? q.next : null;
}
return head.next;
};
Kotlin
/**
* Example:
* var li = ListNode(5)
* var v = li.`val`
* Definition for singly-linked list.
* class ListNode(var `val`: Int) {
* var next: ListNode? = null
* }
*/
class Solution {
fun addTwoNumbers(l1: ListNode, l2: ListNode): ListNode {
val result = ListNode(0)
var current = result
var l1Current: ListNode? = l1
var l2Current: ListNode? = l2
var carry = 0
while (l1Current != null || l2Current != null || carry > 0) {
val sum = (l1Current?.`val` ?: 0) + (l2Current?.`val` ?: 0) + carry
carry = sum / 10
val node = ListNode(sum % 10)
current?.next = node
current = node
l1Current = l1Current?.next
l2Current = l2Current?.next
}
return result.next
}
}
PHP
/**
* Definition for a singly-linked list.
* class ListNode {
* public $val = 0;
* public $next = null;
* function __construct($val = 0, $next = null) {
* $this->val = $val;
* $this->next = $next;
* }
* }
*/
class Solution
{
/**
* @param ListNode $l1
* @param ListNode $l2
* @return ListNode
*/
function addTwoNumbers($l1, $l2)
{
$dummyHead = new ListNode(0);
$p = $l1;
$q = $l2;
$curr = $dummyHead;
$carry = 0;
while ($p || $q || $carry) {
$x = $p ? $p->val : 0;
$y = $q ? $q->val : 0;
$sum = $x + $y + $carry;
$carry = intval($sum / 10);
$curr->next = new ListNode($sum % 10);
$curr = $curr->next;
$p = $p ? $p->next : null;
$q = $q ? $q->next : null;
}
return $dummyHead->next;
}
}
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
dummy_head = ListNode(0)
p = l1
q = l2
curr = dummy_head
carry = 0
while p or q or carry:
x = p.val if p else 0
y = q.val if q else 0
carry, remain = divmod(x + y + carry, 10)
curr.next = ListNode(remain)
curr = curr.next
p = p.next if p else None
q = q.next if q else None
return dummy_head.next
Rust
// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {
pub fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut p = l1;
let mut q = l2;
let mut dummyHead = Some(Box::new(ListNode::new(0)));
let mut curr = dummyHead.as_mut();
let mut carry = 0;
while p.is_some() || q.is_some() || carry > 0{
let mut sum = carry;
if let Some(node) = p {
sum += node.val;
p = node.next;
}
if let Some(node) = q {
sum += node.val;
q = node.next;
}
if let Some(node) = curr {
node.next = Some(Box::new(ListNode::new(sum % 10)));
curr = node.next.as_mut();
}
carry = if sum >= 10 { 1 } else { 0 };
}
return dummyHead.unwrap().next;
}
}
Swift
/**
* Definition for singly-linked list.
* public class ListNode {
* public var val: Int
* public var next: ListNode?
* public init(_ val: Int) {
* self.val = val
* self.next = nil
* }
* }
*/
class Solution {
func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
let dummyHead = ListNode( 0 )
var p = l1, q = l2, curr = dummyHead, carry = 0, r = 0, x = 0, y = 0, sum = 0
while p != nil || q != nil {
x = p?.val ?? 0
y = q?.val ?? 0
sum = x + y + carry
(carry,r) = sum.quotientAndRemainder(dividingBy: 10)
curr.next = ListNode( r )
curr = curr.next!
p = p?.next
q = q?.next
}
if ( carry > 0 ) {
curr.next = ListNode(1)
}
return dummyHead.next
}
}