两数之和
题目要求
编写一个函数，该函数接收两个参数：两个非空链表的头节点。这两个链表代表两个非负整数，它们的位数以逆序方式存储，即链表的第一个节点表示数的个位，第二个节点表示数的十位，以此类推。每个节点只包含一个数字。函数的目标是将这两个数相加，并以同样的链表形式返回它们的和。
解题思路
-
初始化：创建一个新的链表，这个链表将用于存储结果。同时，设置一个变量
carry用于存储进位，初始值为 0。 -
遍历链表：同时遍历两个链表，直到两个链表都到达尾部。对于每一对节点，执行以下操作：
- 将两个节点的值相加，并加上
carry的值。 - 如果相加的结果大于或等于 10，则将
carry设置为 1，并将结果减去 10；否则，将carry设置为 0。 - 将计算的结果作为新节点添加到结果链表中。
- 将两个节点的值相加，并加上
-
处理链表长度不一：如果一个链表比另一个长，需要继续遍历较长的链表，将剩余的节点值加上
carry，并将新节点添加到结果链表中。 -
处理最后的进位：遍历完两个链表后，如果
carry的值为 1，则需要在结果链表的末尾添加一个值为 1 的节点。 -
返回结果：返回新创建的链表的头节点，这个链表就是两个输入链表所代表的数的和。
注意：在实现过程中，需要考虑几个边界情况，例如一个链表为空，或者两个链表的长度不同。此外，当两个链表都遍历完毕后，还需要检查carry是否为 1，如果是，还需要在结果链表的末尾添加一个节点。
Golang 版本
// ListNode 是链表节点的定义。
type ListNode struct {
Val int
Next *ListNode
}
// addTwoNumbers 接受两个链表头节点 l1 和 l2，并返回一个新链表头节点，该链表表示数字之和。
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
// 创建一个哑节点，可以简化对链表的处理，dummyHead.Next 将会是结果链表的头节点。
dummyHead := &ListNode{}
// current 用于指向新链表的当前节点。
current := dummyHead
// carry 表示当前的进位。
carry := 0
// 当 l1 或 l2 还有节点，或者还有进位时，循环继续。
for l1 != nil || l2 != nil || carry > 0 {
// 计算当前位的和。
sum := carry
if l1 != nil {
sum += l1.Val
l1 = l1.Next
}
if l2 != nil {
sum += l2.Val
l2 = l2.Next
}
// 更新进位。
carry = sum / 10
// 创建新节点，值为当前位的和的个位数。
current.Next = &ListNode{Val: sum % 10}
// 移动 current 到下一个节点。
current = current.Next
}
// 返回哑节点的下一个节点，即结果链表的头节点。
return dummyHead.Next
}
这段代码定义了一个ListNode结构体，用于表示链表节点。addTwoNumbers函数接受两个链表的头节点作为输入，创建一个哑节点作为结果链表的前置节点，然后遍历两个输入链表，将对应的节点值相加，并处理进位。最后返回结果链表的头节点。
C++版本
// Definition for singly-linked list.
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
// 创建一个哑节点，可以简化对链表的处理，dummyHead.next 将会是结果链表的头节点。
ListNode *dummyHead = new ListNode(0);
// current 用于指向新链表的当前节点。
ListNode *current = dummyHead;
// carry 表示当前的进位。
int carry = 0;
// 当 l1 或 l2 还有节点，或者还有进位时，循环继续。
while (l1 != nullptr || l2 != nullptr || carry != 0) {
// 计算当前位的和。
int sum = carry;
if (l1 != nullptr) {
sum += l1->val;
l1 = l1->next;
}
if (l2 != nullptr) {
sum += l2->val;
l2 = l2->next;
}
// 更新进位。
carry = sum / 10;
// 创建新节点，值为当前位的和的个位数。
current->next = new ListNode(sum % 10);
// 移动 current 到下一个节点。
current = current->next;
}
// 返回哑节点的下一个节点，即结果链表的头节点。
ListNode *result = dummyHead->next;
delete dummyHead; // 删除哑节点。
return result;
}
};
这段 C++代码定义了一个ListNode结构体，用于表示链表节点，并包含一个构造函数用于初始化节点值。Solution类中的addTwoNumbers成员函数实现了两个数相加的逻辑。函数创建了一个哑节点用于简化链表操作，通过遍历两个输入链表并处理进位来构建结果链表。最后，函数返回结果链表的头节点，并删除了哑节点以避免内存泄漏。
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: ListNode, l2: ListNode) -> ListNode:
# 创建一个哑节点，可以简化对链表的处理，dummy_head.next 将会是结果链表的头节点。
dummy_head = ListNode(0)
# current 用于指向新链表的当前节点。
current = dummy_head
# carry 表示当前的进位。
carry = 0
# 当 l1 或 l2 还有节点，或者还有进位时，循环继续。
while l1 or l2 or carry:
# 计算当前位的和。
sum = carry
if l1:
sum += l1.val
l1 = l1.next
if l2:
sum += l2.val
l2 = l2.next
# 更新进位。
carry, val = divmod(sum, 10)
# 创建新节点，值为当前位的和的个位数。
current.next = ListNode(val)
# 移动 current 到下一个节点。
current = current.next
# 返回哑节点的下一个节点，即结果链表的头节点。
return dummy_head.next
这段 Python 代码定义了一个ListNode类，用于表示链表节点，并包含一个构造函数用于初始化节点值。Solution类中的addTwoNumbers方法实现了两个数相加的逻辑。方法创建了一个哑节点用于简化链表操作，通过遍历两个输入链表并处理进位来构建结果链表。最后，方法返回结果链表的头节点。
Java 版本
// Definition for singly-linked list.
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 创建一个哑节点，可以简化对链表的处理，dummyHead.next 将会是结果链表的头节点。
ListNode dummyHead = new ListNode(0);
// current 用于指向新链表的当前节点。
ListNode current = dummyHead;
// carry 表示当前的进位。
int carry = 0;
// 当 l1 或 l2 还有节点，或者还有进位时，循环继续。
while (l1 != null || l2 != null || carry != 0) {
// 计算当前位的和。
int sum = carry;
if (l1 != null) {
sum += l1.val;
l1 = l1.next;
}
if (l2 != null) {
sum += l2.val;
l2 = l2.next;
}
// 更新进位。
carry = sum / 10;
// 创建新节点，值为当前位的和的个位数。
current.next = new ListNode(sum % 10);
// 移动 current 到下一个节点。
current = current.next;
}
// 返回哑节点的下一个节点，即结果链表的头节点。
return dummyHead.next;
}
}
这段 Java 代码定义了一个ListNode类，用于表示链表节点，并包含几个构造函数用于初始化节点。Solution类中的addTwoNumbers方法实现了两个数相加的逻辑。方法创建了一个哑节点用于简化链表操作，通过遍历两个输入链表并处理进位来构建结果链表。最后，方法返回结果链表的头节点。
Rust 版本
#![allow(unused)] fn main() { // 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 dummy_head = Some(Box::new(ListNode::new(0))); let mut current = &mut dummy_head; let (mut l1, mut l2) = (l1, l2); let mut carry = 0; while l1.is_some() || l2.is_some() || carry != 0 { let sum = match (&l1, &l2) { (Some(node), None) | (None, Some(node)) => { node.val + carry }, (Some(node1), Some(node2)) => { node1.val + node2.val + carry }, (None, None) => carry, }; if let Some(node) = l1 { l1 = node.next; } if let Some(node) = l2 { l2 = node.next; } carry = sum / 10; current.as_mut().unwrap().next = Some(Box::new(ListNode::new(sum % 10))); current = &mut current.as_mut().unwrap().next; } dummy_head.unwrap().next } } }
这段 Rust 代码定义了一个ListNode结构体，用于表示链表节点，并实现了一个new函数用于创建新节点。Solution结构体中的add_two_numbers函数实现了两个数相加的逻辑。函数创建了一个哑节点用于简化链表操作，通过遍历两个输入链表并处理进位来构建结果链表。最后，函数返回结果链表的头节点。
总结
上面给出了使用不同编程语言（包括 Golang、C++、Python、Java 和 Rust）实现的两数相加的链表题目的解法。这道题目的解法思路大致相同，都是通过遍历两个链表，同时处理进位，然后构建新的链表来表示结果。每种语言的具体实现细节略有不同，但核心思想是一致的。这展示了不同编程语言之间的语法和实现风格的差异，同时也展示了这种常见问题的多种解决方法。