# LeetCode Solution, Medium, 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.

## 解法解析

### 解法範例

#### Go

``````/**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
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
}
}
``````

#### JavaScript

``````/**
* 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) {
let p = l1,
q = l2,
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;
}

};
``````

#### Kotlin

``````/**
* Example:
* var li = ListNode(5)
* var v = li.`val`
* 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
*/
{
\$p = \$l1;
\$q = \$l2;
\$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;
}

}
}
``````

#### 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]:
p = l1
q = l2
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

``````

#### 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 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 };
}

}
}
``````

#### Swift

``````/**
* 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)
}