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.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
/**
* Definition for a singly-linked list.
* class ListNode {
* public $val = 0;
* public $next = null;
* function __construct($val) { $this->val = $val; }
* }
*/
// 28ms
class Solution {
/**
* @param ListNode $l1
* @param ListNode $l2
* @return ListNode
*/
function addTwoNumbers($l1, $l2) {
// 进位
$carry = 0;
$nl1 = new ListNode(0);
// 只new一次 为引用赋值
$nl2 = $nl1;
while (isset($l1->val) || isset($l2->val)) {
$l1_val = isset($l1->val) ? $l1->val :0;
$l2_val = isset($l2->val) ? $l2->val :0;
$val = $l1_val + $l2_val + $carry;
if($val >= 10) {
$carry = 1;
$curr_val = $val-10;
} else {
$carry = 0;
$curr_val = $val;
}
// 指针指向下一位
$l1 = $l1->next;
$l2 = $l2->next;
$nl2->next = new ListNode($curr_val);
$nl2 = $nl2->next;
}
if($carry == 1) {
$nl2->next = new ListNode(1);
}
return $nl1->next;
}
}
// 36ms
class Solution {
function addTwoNumbers($l1, $l2) {
$a = new ListNode(0);
$b = $a;
$carry = 0;
while($l1 != NULL || $l2!= NULL || $carry !== 0){
$sum = ($l1 ? $l1->val : 0)+ ($l2 ? $l2->val : 0) + $carry;
if($sum > 9){
$carry = intval($sum / 10);
$remainder = $sum % 10;
$final = $remainder;
}else{
$carry = 0;
$final = $sum;
}
$b = $b->next = new ListNode($final);
$l1 = $l1 ->next;
$l2 = $l2 ->next;
}
return $a->next;
}
}
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
// 12ms
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
l := &ListNode{}
nl := l
carry := 0
for l1 != nil || l2 != nil {
v := 0
if l1 != nil {
v += l1.Val
l1 = l1.Next
}
if l2 != nil {
v += l2.Val
l2 = l2.Next
}
if v+carry >= 10 {
v = v+carry-10
carry = 1
} else {
v = v+carry
carry = 0
}
if l1 == nil && l2 == nil && carry == 0 {
nl.Next = nil
} else {
nl.Next = &ListNode{}
}
nl.Val = v
nl = nl.Next
}
if carry > 0 {
nl.Next = &ListNode{}
nl.Val = 1
nl.Next = nil
}
return l
}
// 24ms
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
carry := 0
head := new(ListNode)
cur := head
for l1 != nil || l2 != nil || carry != 0 {
n1, n2 := 0, 0
if l1 != nil {
n1, l1 = l1.Val, l1.Next
}
if l2 != nil {
n2, l2 = l2.Val, l2.Next
}
num := n1 + n2 + carry
carry = num / 10
cur.Next = &ListNode{Val:num%10, Next:nil}
cur = cur.Next
}
return head.Next
}
方法一一般是自己实现的方法，其他方式是在discuss中查找的更为优秀的方法，用作学习和借鉴。