仿淘宝商城网站开源系统,网站文章在哪发布做seo,网站服务器 试用,宠物网站建设规划书2.两数相加
题目
难度#xff1a;中等
给你两个 非空 的链表#xff0c;表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的#xff0c;并且每个节点只能存储 一位 数字。
请你将两个数相加#xff0c;并以相同形式返回一个表示和的链表。
你可以假设除了数…2.两数相加
题目
难度中等
给你两个 非空 的链表表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的并且每个节点只能存储 一位 数字。
请你将两个数相加并以相同形式返回一个表示和的链表。
你可以假设除了数字 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题目数据保证列表表示的数字不含前导零 思路
小学生加法计算只不过用链表来实现
个位数和个位数相加十位数和十位数相加用carry来进位用current来指向存储结果的链表的当前节点 例子详解
当输入是 l1 [2,4,3] 和 l2 [5,6,4] 时我们将执行 addTwoNumbers 方法中的循环。下面是每个循环迭代的分析 第一次循环 val1 2, val2 5, carry 0currentSum 2 5 0 7carry 0创建新节点 current.next ListNode(7)结果链表[7] 第二次循环 val1 4, val2 6, carry 0currentSum 4 6 0 10carry 1 由于上一位的进位创建新节点 current.next ListNode(0)结果链表[7, 0] 第三次循环 val1 3, val2 4, carry 1currentSum 3 4 1 8carry 0创建新节点 current.next ListNode(8)结果链表[7, 0, 8] 结束循环返回结果链表 [7, 0, 8] 表示 2-4-3 和 5-6-4 相加的结果。
这样每个循环迭代都处理两个链表的当前节点值以及上一位的进位生成一个新节点并将结果连接到结果链表中。 java代码
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode pre new ListNode(0); // 创建一个新的链表pre是其虚拟头节点ListNode current pre; // 创建一个指针current指向当前处理的节点int carry 0; // carry表示进位while(l1 ! null || l2 ! null) { // 当l1或l2不为空时进入循环int x l1 null ? 0 : l1.val; // 如果l1不为空取l1的值否则取0int y l2 null ? 0 : l2.val; // 如果l2不为空取l2的值否则取0int sum x y carry; // 计算当前位的和carry sum / 10; // 更新进位sum sum % 10; // 计算当前位的值current.next new ListNode(sum); // 创建一个新的节点值为sum然后将cur的next指向这个新节点current current.next; // 将current向后移动一位if(l1 ! null)l1 l1.next; // 如果l1不为空将l1向后移动一位if(l2 ! null)l2 l2.next; // 如果l2不为空将l2向后移动一位}if(carry 1) { // 如果最后还有进位current.next new ListNode(carry); // 创建一个新的节点值为carry然后将cur的next指向这个新节点}return pre.next; // 返回结果链表的头节点}
}
