【链表】Leetcode 2. 两数相加【中等】

两数相加

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：
在这里插入图片描述
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

解题思路

可以通过模拟手工相加的过程来实现两个逆序链表的相加。
从链表的头部开始，对应位置的数字相加并考虑进位。

具体步骤

1、初始化一个结果链表 dummyHead 和一个指针 current 指向 dummyHead。
2、初始化进位为 0。
3、遍历两个链表，对应位置的数字相加并加上进位。
4、将结果添加到新链表中，并更新进位。
5、如果两个链表的长度不同，需要考虑短链表的高位是否需要进位。
6、如果最后还有进位，需要在结果链表的最后添加一个新节点。
7、返回结果链表的头部。

Java实现

public class AddTwoNumbers {
	static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode current = dummyHead;
        int carry = 0;//进位值

        while (l1 != null || l2 != null) {
            int x = (l1 != null) ? l1.val : 0;
            int y = (l2 != null) ? l2.val : 0;

            int sum = x + y + carry;
            carry = sum / 10;
            current.next = new ListNode(sum % 10);

            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
            current = current.next;
        }

        if (carry > 0) {
            current.next = new ListNode(carry);
        }

        return dummyHead.next;
    }

    public static void main(String[] args) {
        // 构造链表 342: 2 -> 4 -> 3
        ListNode l1 = new ListNode(2);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(3);

        // 构造链表 465: 5 -> 6 -> 4
        ListNode l2 = new ListNode(5);
        l2.next = new ListNode(6);
        l2.next.next = new ListNode(4);

        // 调用 addTwoNumbers 方法相加链表
        AddTwoNumbers solution = new AddTwoNumbers();
        ListNode result = solution.addTwoNumbers(l1, l2);

        // 打印相加结果
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
        // 输出：7 -> 0 -> 8
    }
}

时间空间复杂度

时间复杂度：O(max(m, n))，其中 m 和 n 分别是两个链表的长度，需要遍历较长的链表。
空间复杂度：O(max(m, n))，需要创建一个新的链表来存储相加后的结果。

java两个大数相加

实现思路类似，从末位逐位相加，进位

public class BigDecimalAdd {

    public static void main(String[] args) {
         String a = "13413";
         String b = "3333";
        System.out.println(add(a,b));
    }

    public static String add(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int carry = 0;
        int i = a.length() - 1;
        int j = b.length() - 1;

        while (i >= 0 || j >= 0 || carry > 0) {
            int sum = carry;
            if (i >= 0) {
                //a.charAt(i--) 等价于 a.charAt(i)执行后，再执行i--;
                //a.charAt(i--) - '0' 数字的ASCII转化成对应数值
                sum += a.charAt(i--) - '0';
            }
            if (j >= 0) {
                sum += b.charAt(j--) - '0';
            }
            sb.append(sum % 10);
            carry = sum / 10;
        }

        return sb.reverse().toString();
    }

}