当前位置： 面试刷题>> 两数相加(经典算法150题)
**题目描述**：
给定两个非空链表，表示两个非负整数。这两个整数是逆序存储的，每个节点包含一个数字。将这两个数相加，并以相同的方式（逆序存储）返回一个新的链表。
**示例**：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
**注意**：
- 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
- 进位需要保留，例如输入为 (1 -> 2 -> 3) + (4 -> 5 -> 6) 时，输出应为 (5 -> 7 -> 9)，而不是 (5 -> 7 -> 9 -> 0)，因为结果不需要额外的零来填充。
**PHP 代码示例**：
```php
class ListNode {
public $val = 0;
public $next = null;
function __construct($val = 0, $next = null) {
$this->val = $val;
$this->next = $next;
}
}
function addTwoNumbers($l1, $l2) {
$dummy = new ListNode(0); // 创建一个哑节点
$current = $dummy; // 当前节点指针
$carry = 0; // 进位
while ($l1 !== null || $l2 !== null || $carry > 0) {
$x = ($l1 !== null) ? $l1->val : 0;
$y = ($l2 !== null) ? $l2->val : 0;
$sum = $x + $y + $carry;
$carry = intval($sum / 10); // 计算进位
$current->next = new ListNode($sum % 10); // 创建新节点存储当前位的和
$current = $current->next; // 移动当前节点指针
if ($l1 !== null) {
$l1 = $l1->next;
}
if ($l2 !== null) {
$l2 = $l2->next;
}
}
return $dummy->next; // 返回哑节点的下一个节点作为结果链表的头节点
}
```
**Python 代码示例**：
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def addTwoNumbers(l1, l2):
dummy = ListNode(0)
current = dummy
carry = 0
while l1 or l2 or carry:
x = l1.val if l1 else 0
y = l2.val if l2 else 0
sum = x + y + carry
carry = sum // 10
current.next = ListNode(sum % 10)
current = current.next
if l1:
l1 = l1.next
if l2:
l2 = l2.next
return dummy.next
```
**JavaScript 代码示例**：
```javascript
function ListNode(val, next) {
this.val = (val===undefined ? 0 : val)
this.next = (next===undefined ? null : next)
}
function addTwoNumbers(l1, l2) {
let dummy = new ListNode(0);
let current = dummy;
let carry = 0;
while (l1 !== null || l2 !== null || carry > 0) {
let x = (l1 !== null) ? l1.val : 0;
let y = (l2 !== null) ? l2.val : 0;
let sum = x + y + carry;
carry = Math.floor(sum / 10);
current.next = new ListNode(sum % 10);
current = current.next;
if (l1 !== null) {
l1 = l1.next;
}
if (l2 !== null) {
l2 = l2.next;
}
}
return dummy.next;
}
```
以上代码均实现了题目要求的功能，即将两个逆序存储的链表表示的非负整数相加，并以逆序链表的形式返回结果。