LeetCode2.AddTwoNumbers两数相加(Java可运行,带测试用例)

发布时间:2024年01月03日

一、题目

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

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

你可以假设除了数字 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
  • 题目数据保证列表表示的数字不含前导零

二、题解

代码:

public class AddTwoNumbers {
    // Definition for singly-linked list.
    static class ListNode {
        int val;
        // 指向链表中下一个节点
        ListNode next;
        // 构造函数,使用一个值初始化节点
        ListNode(int x) { val = x; }

        // 重写方法,方便打印链表
        @Override
        public String toString() {
            return val + (next != null ? " -> " + next.toString() : "");
        }
    }

    static class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            // 定义一个新链表伪指针,用来指向头指针,返回结果
            ListNode pre = new ListNode(0);
            // 定义一个可移动的指针,指向存储两个数之和的位置
            ListNode cur = pre;
            // 存储两个数字相加的进位的值
            int carry = 0;
            // 当l1不等于null或l2不等于空时,就进入循环
            while(l1 != null || l2 != null) {
                // 如果l1不等于null时,就取它的值,等于null时,就赋值0,保持两个链表具有相同的位数
                int x = l1 == null ? 0 : l1.val;
                // 如果l2不等于null时,就取它的值,等于null时,就赋值0,保持两个链表具有相同的位数
                int y = l2 == null ? 0 : l2.val;
                // 将两个链表的值,进行相加,并加上进位数
                int sum = x + y + carry;

                // 计算进位数
                carry = sum / 10;
                // 计算两个数的和,此时排除超过10的请况(大于10,取余数)
                sum = sum % 10;
                // 将求和数赋值给新链表的节点,注意这个时候不能直接将sum赋值给cur.next = sum。这时候会报,类型不匹配。所以这个时候要创一个新的节点,将值赋予节点
                cur.next = new ListNode(sum);

                // 将新链表的节点后移
                cur = cur.next;
                // 当链表l1不等于null的时候,将l1的节点后移
                if(l1 != null) {
                    l1 = l1.next;
                }
                // 当链表l2不等于null的时候,将l2的节点后移
                if(l2 != null) {
                    l2 = l2.next;
                }
            }
            // 如果最后两个数,相加的时候有进位数的时候,就将进位数,赋予链表的新节点。两数相加最多为18,所以的的值最大只能是1
            if(carry == 1) {
                cur.next = new ListNode(carry);
            }
            // 返回链表的头节点
            return pre.next;
        }
    }

    // 主方法,用于测试
    public static void main(String[] args) {
        ListNode l1 = new ListNode(2);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(3);
        l1.next.next.next = new ListNode(6);
        System.out.println("l1: " + l1.toString());

        ListNode l2 = new ListNode(5);
        l2.next = new ListNode(6);
        l2.next.next = new ListNode(4);
        l2.next.next.next = new ListNode(7);
        System.out.println("l2: " + l2.toString());

        Solution solution = new Solution();
        ListNode result = solution.addTwoNumbers(l1, l2);
        // 打印结果链表
        System.out.println("result: " + result.toString());
        /**
         * 输出:
         * l1: 2 -> 4 -> 3 -> 6
         * l2: 5 -> 6 -> 4 -> 7
         * result: 7 -> 0 -> 8 -> 3 -> 1
         */
    }
}

时间复杂度:O(max(m,n)),其中 m 和 n 分别为两个链表的长度,上面算法最多重复max(m,n)次。
空间复杂度:O(max(m,n)),新列表的长度最多为max(m,n)+1

文章来源:https://blog.csdn.net/kkill_youokk_/article/details/135365176
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。