东阳网络科技有限公司_seo外包服务优化_图片识别搜索引擎_搜索引擎平台排名

题目

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

答案解法

要解决这个问题，我们需要逐位处理两个链表中的数字，并将它们相加，同时考虑进位问题。链表是按照逆序存储数字的，所以我们可以从链表的头开始逐位相加，类似手动加法的方式。

解题思路：

逐位相加：从两个链表的头节点开始，每次取出链表的当前节点的值进行相加。
处理进位：如果相加的结果超过 9，就需要进位。保留个位数，并将进位留给下一次相加。
遍历两个链表：当某个链表遍历完毕后，继续处理另一个链表剩下的部分。如果有进位，需要在链表的末尾再加一个节点。
构建新链表：我们需要将相加的结果存储在一个新的链表中。

具体步骤：

使用两个指针分别遍历两个链表。
每次从链表中取出节点值进行相加，同时加上之前的进位。
将计算结果的个位部分存入新链表，并更新进位值。
如果某个链表遍历完，继续处理另一个链表，直到两个链表都遍历结束。如果最后还有进位，则需要增加一个节点。

代码实现：

#include <iostream>// 定义链表节点结构
struct ListNode {int val; // 存储当前节点的值ListNode* next; // 指向下一个节点的指针ListNode(int x) : val(x), next(nullptr) {}
};class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {// 创建一个哑节点(dummy node)，方便处理ListNode* dummy = new ListNode(0);ListNode* curr = dummy;int carry = 0; // 进位// 遍历两个链表while (l1 != nullptr || l2 != nullptr) {int x = (l1 != nullptr) ? l1->val : 0; // 链表1当前节点的值int y = (l2 != nullptr) ? l2->val : 0; // 链表2当前节点的值int sum = x + y + carry; // 当前位的和，加上进位carry = sum / 10; // 计算进位curr->next = new ListNode(sum % 10); // 新链表存储当前位的结果curr = curr->next; // 移动到下一个节点// 移动l1和l2到下一个节点if (l1 != nullptr) l1 = l1->next;if (l2 != nullptr) l2 = l2->next;}// 如果最后还有进位，增加一个节点if (carry > 0) {curr->next = new ListNode(carry);}return dummy->next; // 返回新链表的头节点}
};// 打印链表
void printList(ListNode* node) {while (node != nullptr) {std::cout << node->val << " ";node = node->next;}std::cout << std::endl;
}int main() {// 创建两个链表：表示数字 342 (链表存储为 2 -> 4 -> 3)ListNode* l1 = new ListNode(2);l1->next = new ListNode(4);l1->next->next = new ListNode(3);// 创建另一个链表：表示数字 465 (链表存储为 5 -> 6 -> 4)ListNode* l2 = new ListNode(5);l2->next = new ListNode(6);l2->next->next = new ListNode(4);Solution sol;ListNode* result = sol.addTwoNumbers(l1, l2);// 输出相加后的链表结果：7 -> 0 -> 8 (对应的数字是 807)printList(result);return 0;
}

代码解释：

链表节点结构：使用 ListNode 结构表示链表节点，每个节点存储一个数值，并指向下一个节点。
addTwoNumbers 函数：
- 使用哑节点 dummy 方便处理结果链表。
- 使用 carry 变量存储进位值。
- 遍历链表 l1 和 l2，每次取出两个链表对应位置的数字进行相加，并处理进位。
- 如果链表长度不同，可以使用 0 作为短链表的补充位。
- 最后如果有进位，还需要再加一个节点。
printList 函数：用于打印链表中的值，方便查看输出结果。

什么是哑节点？

在链表操作中，哑节点（dummy node）是一个技巧性用法，通常用于简化代码逻辑，特别是在处理边界条件时，比如头节点的特殊处理。哑节点是一个初始化时附加的虚拟节点，通常不存储任何有意义的数据。它的主要作用是方便地处理链表的开头，使代码更加统一、简洁。
ListNode* dummy = new ListNode(0);
在这段代码中，我们创建了一个值为 0 的哑节点。这个节点的值其实无关紧要，它的存在只是为了帮助我们处理链表的头节点（第一位）的相加操作。
哑节点的 next 指针会指向结果链表的第一个有效节点。最终我们返回的链表是从 dummy->next 开始的。
在这里插入图片描述
因为遍历到最后，新指针在尾部，这时候返回头节点就很方便，体现出哑节点的好处来了。