炫酷的网站,做网站和APP需要注册公司吗,网站设置超链接代码,广告制作合同范本免费一、题目描述
给定两个用链表表示的整数#xff0c;每个节点包含一个数位。 这些数位是反向存放的#xff0c;也就是个位排在链表首部。 编写函数对这两个整数求和#xff0c;并用链表形式返回结果。 示例#xff1a;
输入#xff1a;(7 - 1 - 6) (5 - 9 -…一、题目描述
给定两个用链表表示的整数每个节点包含一个数位。 这些数位是反向存放的也就是个位排在链表首部。 编写函数对这两个整数求和并用链表形式返回结果。 示例
输入(7 - 1 - 6) (5 - 9 - 2)即617 295
输出2 - 1 - 9即912输入(1) (9 - 9)即199
输出0 - 0 - 1即100二、题解
思路因为链表是按照个位十位百位逆序存储的所以直接顺序遍历链表第一个就是个位接着十位百位等。两个链表的值相加存储作为一个新节点存储进位信息单独存到一个变量中每次都加上这个进位信息。 遍历操作使用两个指针遍历
一个指针head指向一开始的头节点保存链表一个指针last指向上一次的节点依次往后移动
进位及存储的元素判断
判断是否有进位两个节点的和/10 如果是0则没有进位如果是1则有进位。如果相加是超过了10即存在进位信息那么存储在当前节点的值就是余数 两个节点的和%10 class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {//进位标志int carry 0;//开头的节点ListNode head null;//指向上一个节点ListNode last null;while (l1 ! null || l2 ! null){int val (l1 null ? 0 : l1.val) (l2 null ? 0 : l2.val);//该位置上的数int cur val carry;Integer remainder null;if ((cur / 10) 0) {//有进位 余数remainder cur % 10;}//求和之后的新节点ListNode newNode new ListNode(remainder ! null ? remainder : cur);if (head null) {//一开始的头节点head newNode;} else {last.next newNode;}last newNode;//存储进位信息 给下一次相加使用carry cur / 10;l1 (l1 null ? null : l1.next);l2 (l2 null ? null : l2.next);}//循环结束了如果carry还有值说明最后还进了一位再增加一个节点if (carry 1) {last.next new ListNode(carry, null);}return head;}
}
