网站建站实训总结,wordpress 分享 点赞,汾阳今天重大新闻,陕西网站维护一、提出问题 给你两个非空的链表#xff0c;表示两个非负的整数。它们每位数字都是按照逆序的方式存储的#xff0c;并且每个节点只能存储一位数字。请你将两个数相加#xff0c;并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外#xff0c;这两个数都不会以…一、提出问题 给你两个非空的链表表示两个非负的整数。它们每位数字都是按照逆序的方式存储的并且每个节点只能存储一位数字。请你将两个数相加并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外这两个数都不会以 0 开头。 示例 1 输入l1 [2,4,3], l2 [5,6,4]
输出[7,0,8]
解释342 465 807.示例 2 输入l1 [0], l2 [0]
输出[0]示例 3 输入l1 [9,9,9,9,9,9,9], l2 [9,9,9,9]
输出[8,9,9,9,0,0,0,1]提示 每个链表中的节点数在范围 [1, 100] 内0 Node.val 9题目数据保证列表表示的数字不含前导零二、解决问题 1思路 可以通过模拟计算过程得到解答。 由于是逆序的两个链表中同一位置的数字可以直接相加。如果两个链表的长度不同则可以认为长度短的链表的后面有若干个0 。注意相加的时候可能会产生进位。如果链表遍历结束后还有进位则需要在答案链表的后面附加一个节点节点的值就是 carry其实就是1。 2代码 struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {struct ListNode *head NULL, *tail NULL;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 malloc(sizeof(struct ListNode));tail-val sum % 10;tail-next NULL;} else {tail-next malloc(sizeof(struct ListNode));tail-next-val sum % 10;tail tail-next;tail-next NULL;}carry sum / 10;if (l1) {l1 l1-next;}if (l2) {l2 l2-next;}}if (carry 0) {tail-next malloc(sizeof(struct ListNode));tail-next-val carry;tail-next-next NULL;}return head;
} 3复杂度 时间复杂度O(max(m,n))其中 m 和 n 分别为两个链表的长度。我们要遍历两个链表的全部位置而处理每个位置只需要 O(1) 的时间。空间复杂度O(1)。注意返回值不计入空间复杂度。三、回顾总结 1注意代码中对头结点的处理技巧如果不保存好head指针后面会丢失的。 2这是一道逐位相加的题目。网友总结了一套模板来解答逐位相加的题目。 while ( A 没完 || B 没完)
{A 的当前位B 的当前位和 A 的当前位 B 的当前位 进位carry当前位 和 % 10;进位 和 / 10;更新A、B
}判断是否还有进位
