将由链表表示的两个数字相加
### 将由链表表示的两个数字相加：C/C++实现与算法解析
在计算机科学中，链表是一种基础且重要的数据结构，尤其在处理动态数据或不确定长度的序列时，链表展现出其独特的优势。本文将深入探讨一个经典问题：**如何将两个用链表表示的非负整数相加**，并返回它们的和链表。这个问题不仅考察了链表的基本操作，还涉及算法设计与优化，是面试和编程竞赛中的高频考点。
#### 问题描述
给定两个非空链表，分别表示两个非负整数。数字的每一位存储在链表的节点中，且数字以逆序方式存储（即个位在链表头部，十位在次节点，依此类推）。例如：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807我们的任务是编写一个函数，接收这两个链表的头节点，返回一个新链表，表示这两个数的和。
#### 链表基础回顾
在深入解决问题之前，让我们回顾一下链表的基本概念。链表是一种线性数据结构，其中的元素不是在内存中连续存放的，而是通过指针（或引用）连接起来。每个节点包含两部分：数据和指向下一个节点的指针。单链表的定义通常如下（以C++为例）：
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};链表的操作包括遍历、插入、删除等，其中遍历是最基础的操作，通常通过一个指针从头节点开始，依次访问每个节点直到末尾（`next`为`nullptr`）。
#### 解题思路
针对这个问题，我们可以采用**逐位相加并处理进位**的策略。具体步骤如下：
初始化一个哑节点（dummy node）作为结果链表的起始点，这样可以简化链表头部的处理。
使用一个指针`current`指向哑节点，用于构建结果链表。
初始化进位`carry`为0。
同时遍历两个链表`l1`和`l2`，直到两者都到达末尾且进位为0。
在每一步中，计算当前位的和（包括进位）：`sum = l1->val + l2->val + carry`。
更新进位：`carry = sum / 10`。
创建新节点，其值为`sum % 10`，并将其链接到`current`的后面。
移动`l1`、`l2`和`current`指针到下一个节点。
如果其中一个链表已经遍历完，则将另一个链表的剩余部分继续相加。
最后，如果进位不为0，需要创建一个新节点存储进位值。
返回哑节点的下一个节点，即结果链表的头节点。
#### C++实现
基于上述思路，以下是C++的实现代码：
#include
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode dummy(0); // 哑节点
ListNode* current = &dummy;
int carry = 0;
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->next;
}
return dummy.next;
} #### 代码解析
1. **哑节点**：使用哑节点可以避免处理空链表或链表头部插入的特殊情况，使代码更加简洁。
2. **循环条件**：`while (l1 != nullptr || l2 != nullptr || carry != 0)`确保即使一个链表已经遍历完，只要还有进位或另一个链表未遍历完，就继续处理。
3. **逐位相加**：在每次循环中，计算当前位的和（包括进位），然后更新进位和结果链表。
4. **创建新节点**：使用`new`操作符动态分配内存，创建存储当前位和（模10）的新节点，并链接到结果链表。
#### 边界条件与测试
在编写代码时，需要考虑多种边界条件，以确保算法的鲁棒性。常见的边界条件包括：
一个链表比另一个长。
相加结果有额外的进位（如999 + 1 = 1000）。
两个链表都为空（根据题意，题目已说明非空，但实际实现中可能需要考虑）。
测试用例示例：
// 测试用例1: 342 + 465 = 807
ListNode* l1 = new ListNode(2);
l1->next = new ListNode(4);
l1->next->next = new ListNode(3);
ListNode* l2 = new ListNode(5);
l2->next = new ListNode(6);
l2->next->next = new ListNode(4);
ListNode* result = addTwoNumbers(l1, l2);
// 输出结果链表: 7 -> 0 -> 8
// 测试用例2: 0 + 0 = 0
ListNode* l3 = new ListNode(0);
ListNode* l4 = new ListNode(0);
ListNode* result2 = addTwoNumbers(l3, l4);
// 输出结果链表: 0
// 测试用例3: 999 + 1 = 1000
ListNode* l5 = new ListNode(9);
l5->next = new ListNode(9);
l5->next->next = new ListNode(9);
ListNode* l6 = new ListNode(1);
ListNode* result3 = addTwoNumbers(l5, l6);
// 输出结果链表: 0 -> 0 -> 0 -> 1#### 复杂度分析
- **时间复杂度**：O(max(n, m))，其中n和m分别是两个链表的长度。我们需要遍历较长的链表，或者直到进位为0。
- **空间复杂度**：O(max(n, m))，结果链表的长度最多为max(n, m) + 1（如果有进位）。
#### 优化与变种
虽然上述解法已经相当高效，但仍有优化空间或变种问题值得探讨：
**原地修改链表**：如果允许修改输入链表，可以尝试在其中一个链表上直接修改，减少空间使用。但这种方法通常不推荐，因为会破坏原始数据。
**正序存储数字**：如果数字是正序存储的（即个位在链表尾部），则需要先反转链表，相加后再反转结果链表。这增加了时间复杂度，但展示了链表反转的应用。
**大数相加**：将链表视为大数的表示，可以扩展到任意长度的整数相加，适用于密码学或高精度计算领域。
#### 链表反转示例（正序存储数字的变种）
假设数字是正序存储的，我们需要先反转链表：
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr != nullptr) {
ListNode* nextTemp = curr->next;
curr->next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
ListNode* addTwoNumbersOrdered(ListNode* l1, ListNode* l2) {
l1 = reverseList(l1);
l2 = reverseList(l2);
ListNode* result = addTwoNumbers(l1, l2); // 使用之前的addTwoNumbers函数
result = reverseList(result);
return result;
}#### 总结与扩展
本文详细探讨了如何将两个用链表表示的非负整数相加的问题，从问题描述、链表基础、解题思路到C++实现，逐步深入。通过逐位相加并处理进位的方法，我们能够高效地解决这个问题。同时，我们也讨论了边界条件、复杂度分析以及变种问题，如正序存储数字的处理。
链表作为基础数据结构，在算法设计中扮演着重要角色。掌握链表的操作不仅有助于解决此类数学问题，还能为更复杂的算法（如图算法、动态规划等）打下坚实基础。希望本文能为读者提供有价值的参考，激发对数据结构与算法的深入探索。
关键词：链表、数字相加、C++实现、逐位相加、进位处理、哑节点、复杂度分析、链表反转
简介：本文详细探讨了如何将两个用链表表示的非负整数相加的问题，从问题描述、链表基础、解题思路到C++实现逐步深入，并分析了边界条件、复杂度及变种问题，如正序存储数字的处理。
