《[02] 两数相加》

发表于 分类于 阅读次数： 本文字数： 701 阅读时长 ≈ 3 分钟
个人公众号

《LeetCode:[02] 两数相加》

《LeetCode：[02]两数相加》

力扣（LeetCode）官网 - 两数相加

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

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

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

示例 1：

img

1
2
3
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807

示例 2：

1
2
输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

1
2
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

方法签名

1
2
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {   
}

“Add Two Numbers” 是一个中等难度的问题，涉及链表的操作。

这个问题的描述是：你有两个非空的链表，代表两个非负的整数。它们的每个节点都包含一个数字。数字以相反的顺序存储，每个节点包含一个数字。你需要将这两个数相加，并将它们作为一个链表返回。

问题的关键在于处理链表的遍历和进位。下面是使用 Java 实现的一个解决方案

知识储备

解题思路

  1. 创建虚拟头节点：使用一个虚拟头节点 dummyHead 来简化边界情况的处理，这样每个节点都可以统一处理。
  2. 遍历链表：同时遍历两个链表 l1 和 l2，直到两者都到达尾部。
  3. 计算和与进位：每一步计算两个节点的和，加上前一步的进位（如果有的话）。新的进位是和除以 10 的结果，而新节点的值是和对 10 的余数。
  4. 创建新节点：为每一步的和创建一个新的节点，并将其添加到当前节点的 next。
  5. 移动指针：移动 l1、l2 和 curr 指针。
  6. 检查最后的进位：如果最后还有进位（大于 0），需要创建一个新的节点。
  7. 返回结果：因为 dummyHead 是虚拟头节点，所以返回 dummyHead.next。

这个解法的时间复杂度是 O (max (n, m))，其中 n 和 m 分别是两个链表的长度。空间复杂度是 O (max (n, m))，主要用于存储新链表。

Java 解决方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

    class Solution {
        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);
                current = current.next;
                if (l1 != null) {
                    l1 = l1.next;
                }
                if (l2 != null) {
                    l2 = l2.next;
                }
            }
            // 额外处理进位
            if (carry != 0) {
                current.next = new ListNode(carry);
            }
            return dummyHead.next;
        }
    }

动画 GIF 演示

img