上海网站设计外包,在线查询企业,网站的程序和数据库怎么做,制作网站参考案例文章目录 写在前面Tag题目来源题目解读解题思路方法一#xff1a;模拟 其他语言python3 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法#xff0c;两到三天更新一篇文章#xff0c;欢迎催更…… 专栏内容以分析题目为主#xff0c;并附带一些对于本题涉及到… 文章目录 写在前面Tag题目来源题目解读解题思路方法一模拟 其他语言python3 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法两到三天更新一篇文章欢迎催更…… 专栏内容以分析题目为主并附带一些对于本题涉及到的数据结构等内容进行回顾与总结文章结构大致如下部分内容会有增删 Tag介绍本题牵涉到的知识点、数据结构题目来源贴上题目的链接方便大家查找题目并完成练习题目解读复述题目确保自己真的理解题目意思并强调一些题目重点信息解题思路介绍一些解题思路每种解题思路包括思路讲解、实现代码以及复杂度分析知识回忆针对今天介绍的题目中的重点内容、数据结构进行回顾总结。 Tag
【单向链表】【数组】 题目来源
2. 两数相加 题目解读
对两个链表对应位置进行相加最后返回结果链表的头结点。 解题思路
很多同学对链表操作不是很熟悉但是对数组操作确实很熟悉于是会想到先将两个链表中的值分别存入到两个数组中然后对数组对应位置进行相加操作得到一个新的数组最后将新的数组转化成链表。该方法就是将自己不熟悉领域的问题转化成熟悉的领域问题求解方然可以解决问题。但是链表也是一种基本的数据结构因此我们有必要掌握并使用链表来解决相关的问题因此接下来将对使用链表的方法进行详细阐述。
关于数组的解答方法大家可以自行尝试并试着分析以下几个问题前两个问题也是接下来 模拟 的方法需要考虑的问题。
转化后的两个数组长度不一样对应为如何相加即一个链表的节点非空另一个链表节点为空的情况。遇到两数相加和超过 9如何进位使用数组方法解决的空间复杂度是多少还可不可以优化
方法一模拟
首先需要考虑几个问题
一个链表的节点非空另一个链表对应位置节点为空时怎么相加很简单空节点对应的数值我们就加上 0对应节点值相加大于 9如何进位我们需要维护一个进位变量 carry表示当前需要进位多少每次节点对应值相加计算需要加上 carry相加结束后更新 carry。
解决以上的两个问题之后开始模拟计算
初始化 carry 0迭代枚举两个链表中的节点直到两个链表都被遍历完毕再退出 while() 循环在循环中两个节点分别记为 l1 和 l2当前需要进位的值为 carry相加后的值定义为 sum 如果 head1 为空sum (0 l2-val carry) % 10curry (0 l2-val carry) / 10如果 head2 为空sum (l1-val 0 carry) % 10curry (0 l1-val 0 carry) / 10如果二者均非空sum (l1-val l2-val carry) % 10curry (l1-val l2-val carry) / 10根据 sum 在需要返回的链表中建立节点。 更新当前节点为下一个节点最后如果 carry 0不要忘记还要新建一个节点。
实现代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode *head nullptr, *tail nullptr;int carry 0;while (l1 || l2) {int n1 l1 ? l1-val : 0;int n2 l2 ? l2-val : 0;int sum n1 n2 carry;if (!head) {head tail new ListNode(sum % 10);}else {tail-next new ListNode(sum % 10);tail tail-next;}carry sum / 10;if (l1) {l1 l1-next;}if (l2) {l2 l2-next;}}if (carry 0) {tail-next new ListNode(carry);}return head;}
};复杂度分析
时间复杂度 O ( m a x ( m , n ) ) O(max(m, n)) O(max(m,n)) m m m 和 n n n 分别为两个链表的长度。
空间复杂度 O ( 1 ) O(1) O(1)返回值不计入空间复杂度。 其他语言
python3
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) - Optional[ListNode]:dummy p ListNode(None)s 0 # carry 值while l1 or l2 or s:s (l1.val if l1 else 0) (l2.val if l2 else 0)p.next ListNode(s % 10)p p.nexts // 10l1 l1.next if l1 else Nonel2 l2.next if l2 else Nonereturn dummy.next写在最后
如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度方法欢迎评论区交流。
最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。
