侧边栏壁纸
博主头像
疯狂IT人博主等级

IT编程日记是一个记录分享程序员【疯狂IT人】编程日记的技术博客,用程序员视角总结分享IT编程和互联网知识的那些事儿。

  • 累计撰写 164 篇文章
  • 累计创建 14 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

JAVA经典题库:2. 两数相加

疯狂IT人
2022-10-27 / 0 评论 / 2 点赞 / 82 阅读 / 636 字 / 正在检测是否收录...

题目

给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。

请你将两个数相加,并以相同形式返回一个表示和的链表。

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

示例 1:
addtwonumber1

输入: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
题目数据保证列表表示的数字不含前导零

文字题解

方法一:模拟

思路与算法

由于输入的两个链表都是逆序存储数字的位数的,因此两个链表中同一位置的数字可以直接相加。

我们同时遍历两个链表,逐位计算它们的和,并与当前位置的进位值相加。具体而言,如果当前两个链表处相应位置的数字为 n1,n2,进位值为carry,则它们的和为 n1+n2+carry;其中,答案链表处相应位置的数字为 (n1+n2+carry)mod10,而新的进位值为
(n1+n2+carry)/10 。

如果两个链表的长度不同,则可以认为长度短的链表的后面有若干个 0 。

此外,如果链表遍历结束后,有 carry>0,还需要在答案链表的后面附加一个节点,节点的值为 carry。

代码

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null, tail = null;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            int sum = n1 + n2 + carry;
            if (head == null) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (carry > 0) {
            tail.next = new ListNode(carry);
        }
        return head;
    }
}

复杂度分析

时间复杂度:O(max(m,n)),其中 m 和 n 分别为两个链表的长度。我们要遍历两个链表的全部位置,而处理每个位置只需要 O(1) 的时间。

空间复杂度:O(1)。注意返回值不计入空间复杂度。

2

评论区