题目
给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 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 开始的。
因为遍历到最后,新指针在尾部,这时候返回头节点就很方便,体现出哑节点的好处来了。
示例解释:
假设我们有两个链表:
l1
表示数字 342(存储为 2 -> 4 -> 3)l2
表示数字 465(存储为 5 -> 6 -> 4)
这两个数字相加是 342 + 465 = 807。相加后的链表应该是 7 -> 0 -> 8,代表数字 807,输出正确。
总结:
这个算法的时间复杂度是 O(max(m, n)),其中 m 和 n 是两个链表的长度,因为我们只需要遍历链表一次。空间复杂度也是 O(max(m, n)),因为我们创建了一个新的链表来存储结果。
如何用链表去构造数?
循环遍历,然后每一个取下来依次累加
但是涉及到进位的问题
如何创建一个链表?
在 C++ 中创建一个链表,通常需要定义链表节点的结构体,并通过指针来连接这些节点。链表的每个节点包含两个部分:一个存储数据的部分和一个指向下一个节点的指针。
创建一个新链表其实就是创建一个头节点。
结构体怎么定义?
struct{
node* l1;
}
一个数据值和下一个指针,还有构造函数
new一个,创建头节点,然后指针指向头结点
为什么ListNode这个号是在listnode上面而不是在后面的next上面?
ListNode* 组合表示指针的类型,意思是这是一个指向 ListNode 类型对象的指针。
在 C++ 中,指针的类型是放在变量名之前的,而不是放在变量名的后面。
链表指针如何取值?
l1->val
如何移动节点
使用判断语句和next完成移动
nullptr是什么?
nullptr 是 C++11 引入的一种特殊关键字,用于表示空指针。它的目的是替代之前的 NULL 宏,提供一种类型安全的空指针表示法。
如何完成进位操作
这道题的关键点?
两数相加这道题目(LeetCode 第 2 题)的关键点主要集中在以下几个方面:
- 链表表示的数字逆序存储
- 链表中的数字是按照 逆序 存储的,这意味着链表的第一个节点是最低位的数字。
- 在处理加法时,我们从链表头部开始,也就是从最低位开始进行加法,这与我们平时的加法运算相符,从个位开始相加。
- 逐位相加并处理进位
- 两个链表的数字需要逐位相加。每个位的和可能会超过 9,因此需要处理进位。
- 进位的处理方式是:当前位相加后,和超过 9 的部分要进到下一位,同时保留个位部分在当前节点中。
- 不同长度链表的处理
- 两个链表可能长度不一致,可能其中一个链表已经处理完,而另一个链表还没处理完。在这种情况下,继续处理较长链表剩余的部分。
- 如果其中一个链表结束,应该视其对应位为
0
来继续计算。
- 最终处理进位
- 当两个链表都处理完后,可能还会有一个进位需要加入到新的链表中。例如,
9 + 9 = 18
,此时要在最后创建一个新的节点,存储进位1
。
关键算法流程
- 遍历两个链表,每次取出两个链表对应位置的数字(如果有的话),相加,并考虑之前是否有进位。
- 如果和超过 9,取其个位部分放到当前节点中,进位部分留给下一次相加。
- 一直遍历,直到两个链表都处理完。如果最后还有进位,创建一个新的节点来存储。
关键点总结:
- 逆序存储的链表:从低位开始相加,符合我们的加法习惯。
- 逐位相加处理进位:每次计算一个节点的值,并将进位保存到下一次的加法运算中。
- 处理不同长度的链表:确保即使两个链表长度不同,也可以正确处理多余的部分。
- 最后的进位:当遍历结束时,如果还有进位,需要在结果链表中加上一个新的节点。
这就是这道题的核心逻辑所在。