内容简介:给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。 如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外,这两个数都不会以 0 开头。输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)输出:7 -> 0 -> 8
给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。 如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
输入:(8 -> 4 -> 9) + (5 -> 6 -> 3)
输出:3 -> 1 -> 3 -> 1
解题方法
初等数学
简单的数学相加即可,不过需要处理几个特殊情况,当两个链表长度不同时,短链表下一位数据用0填充
在两个链接相加的过程中,增加一个变量,用于记录低位和像高位的进位情况,在两个链表遍历后,在查看此值,决定是否添加高位.
图解相关思路
这里输入的两个链表分别为8->4->9和5->6->3
同时取出两个钟列表的第一个元素,计算sum =13,因为result只记录当前个位数据,通过sum%10得到个位内容,添加到结果链表尾部,同时计算进位标识carry = sum/10 = 1.
重复上面步骤,将1插入结果链表尾部,计算carry = 1
重复上面步骤,将3插入结果链表尾部,计算carry = 1
当L1和L2都遍历结束后,检查carry的内容,发现此时carry非0,则尾插一个carry作为高位的内容
代码实现
public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode result = new ListNode(0); ListNode temp = result; int carry = 0; while (l1 != null || l2 != null) { int a = (l1 != null) ? l1.val : 0; int b = (l2 != null) ? l2.val : 0; int sum = carry + a + b; carry = sum / 10; temp.next = new ListNode(sum % 10); temp = temp.next; if (l1 != null) l1 = l1.next; if (l2 != null) l2 = l2.next; } if (carry > 0) { temp.next = new ListNode(carry); } return result.next; } 复制代码
相关代码 欢迎大家关注并提出改进的建议
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。