当前位置: 首页> 文旅> 酒店 > 东阳网络科技有限公司_seo外包服务优化_图片识别搜索引擎_搜索引擎平台排名

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

时间:2025/7/10 20:18:03来源:https://blog.csdn.net/qq_43920838/article/details/142965436 浏览次数:0次
东阳网络科技有限公司_seo外包服务优化_图片识别搜索引擎_搜索引擎平台排名

题目

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

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

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

答案解法

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

解题思路:

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

具体步骤:

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

代码实现:

#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;
}

代码解释:

  1. 链表节点结构:使用 ListNode 结构表示链表节点,每个节点存储一个数值,并指向下一个节点。
  2. addTwoNumbers 函数
    • 使用哑节点 dummy 方便处理结果链表。
    • 使用 carry 变量存储进位值。
    • 遍历链表 l1l2,每次取出两个链表对应位置的数字进行相加,并处理进位。
    • 如果链表长度不同,可以使用 0 作为短链表的补充位。
    • 最后如果有进位,还需要再加一个节点。
  3. 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 题)的关键点主要集中在以下几个方面:

  1. 链表表示的数字逆序存储
  • 链表中的数字是按照 逆序 存储的,这意味着链表的第一个节点是最低位的数字。
  • 在处理加法时,我们从链表头部开始,也就是从最低位开始进行加法,这与我们平时的加法运算相符,从个位开始相加。
  1. 逐位相加并处理进位
  • 两个链表的数字需要逐位相加。每个位的和可能会超过 9,因此需要处理进位
  • 进位的处理方式是:当前位相加后,和超过 9 的部分要进到下一位,同时保留个位部分在当前节点中。
  1. 不同长度链表的处理
  • 两个链表可能长度不一致,可能其中一个链表已经处理完,而另一个链表还没处理完。在这种情况下,继续处理较长链表剩余的部分。
  • 如果其中一个链表结束,应该视其对应位为 0 来继续计算。
  1. 最终处理进位
  • 当两个链表都处理完后,可能还会有一个进位需要加入到新的链表中。例如,9 + 9 = 18,此时要在最后创建一个新的节点,存储进位 1

关键算法流程

  • 遍历两个链表,每次取出两个链表对应位置的数字(如果有的话),相加,并考虑之前是否有进位。
  • 如果和超过 9,取其个位部分放到当前节点中,进位部分留给下一次相加。
  • 一直遍历,直到两个链表都处理完。如果最后还有进位,创建一个新的节点来存储。

关键点总结:

  1. 逆序存储的链表:从低位开始相加,符合我们的加法习惯。
  2. 逐位相加处理进位:每次计算一个节点的值,并将进位保存到下一次的加法运算中。
  3. 处理不同长度的链表:确保即使两个链表长度不同,也可以正确处理多余的部分。
  4. 最后的进位:当遍历结束时,如果还有进位,需要在结果链表中加上一个新的节点。

这就是这道题的核心逻辑所在。

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

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: