middle的编程用法_java

当前位置：网站建设 > 技术支持

资料来源：网络整理时间：2023/3/9 3:56:49 共计：3570 浏览

middle的编程用法？

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)

输出：7 -> 0 -> 8

原因：342 + 465 = 807

思路：

本题是通过链表的方式来实现两个数相加，链表是逆序存储值的，所以可以从前向后依次相加，将相加的值组成一个新的链表返回即可。

要注意的地方：

相加的和为：sumVal= l1val + l2val + carry

存在进位为：carry= sumVal / 10

当任意链表遍历到底时，即该链表val值为null时，要将值置为 0

必须当链表的值都为null并且进位为0时，才可以停止循环

新节点的值为 sumVal % 10

代码：

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

ListNode root = new ListNode(0);

ListNode cursor = root;

int carry = 0;

while(l1 != null || l2 != null || carry != 0) {

int l1Val = l1 != null ? l1.val : 0;

int l2Val = l2 != null ? l2.val : 0;

int sumVal = l1Val + l2Val + carry;

carry = sumVal / 10;

ListNode sumNode = new ListNode(sumVal % 10);

cursor.next = sumNode;

cursor = sumNode;

if(l1 != null) l1 = l1.next;

if(l2 != null) l2 = l2.next;

}

return root.next;

}

复杂度分析：

时间复杂度：O(max(m,n)) ,m和n分别为l1和l2元素的个数，最多遍历次数为l1和l2最长的长度。

空间复杂度：O(max(m,n))+1 ，因为存在进位，所以root链表的值最长会比l1和l2最长长度多1

版权说明：
本网站凡注明“广州京杭原创”的皆为本站原创文章，如需转载请注明出处！
本网转载皆注明出处，遵循行业规范，如发现作品内容版权或其它问题的，请与我们联系处理！
欢迎扫描右侧微信二维码与我们联系。