LeetCode - 445 - 两数相加|| - java - 细喔

LeetCode - 445 - 两数相加|| - java - 细喔

文章目录

• 前身
• 题目
• 题目解析
• 解题过程
• • 首先我们为 题目的两个链表，各自创建一个栈。
  • 然后便是将 ListNode l1 和 ListNode l2 两个节点的val值，分别存入两个“栈”。
  • 接下来，就是出栈，将两个链表对应val值相加，加上 上一个节点的 进位数 carry(逢十进一)，得到sum和，再来求 sum 的个位数（sum%10），因为每个节点只能存储一位数。再根据这个值（sum%10），去new一个节点。顺便在讲carry值，更新（sum/10）。
• 代码如下
• • 代码细节（不多，只有一个）

前身

LeetCode - 2 - 相加

题目

---

 

题目解析

就是说 从两个链表尾结点的val开始相加，且一个节点的val域，只能存储一位数。也就是说十进制：逢十进一。与前身题，不同在就于逆序。难点就在这里。
这里我们的解题思维是利用栈的特性：先入后出，后入先出。

---

 

解题过程 首先我们为 题目的两个链表，各自创建一个栈。

我之所以使用 deque(双向队列)是因为,是因为我们想提升效率。（我也试了一下，如果是new了两个栈Stack【Stack stack = new Stack()】，空间效率大，占用空间比较大）。而使用双向队列的目标就是提升空间效率（效果跟栈是一样的）。至于后面new了个 linkedList 链表，你们应该看得懂，我们这题是链表题， *** 作的是链表数据。
而且，你看看下标图， deque 是 linkedList 的父类。父类引用子类对象，也可以！（向上提升）

---

 

然后便是将 ListNode l1 和 ListNode l2 两个节点的val值，分别存入两个“栈”。

---

 

接下来，就是出栈，将两个链表对应val值相加，加上 上一个节点的 进位数 carry(逢十进一)，得到sum和，再来求 sum 的个位数（sum%10），因为每个节点只能存储一位数。再根据这个值（sum%10），去new一个节点。顺便在讲carry值，更新（sum/10）。

细节部分： 因为我们现在是逆序相加，所以我们carry进位数，一开始是 0 。而且需要定义在外面，不然每次循环都需要创建一个 carry 浪费时间和空间。（至于为什么需要循环，你可以想想，光是把两个栈里的数据拿出来，是不是就需要一个循环，你要一个个写，那当我没说。）。另外，我们需要new 一个新的头节点head，并初始化为null，用它来进行逆序链接链表的节点，并且最终作为新链表的头节点。最后返回这个head。我们这题就算完成了！

---

 

代码如下

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Deque stack1 = new linkedList<>();
        Deque stack2 = new linkedList<>();

        while(l1 != null){
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while(l2 != null){
            stack2.push(l2.val);
            l2 = l2.next;
        }
        int carry = 0;// 进位数
        ListNode head = null;// 头节点
        while(!stack1.isEmpty() || !stack2.isEmpty() || carry > 0){
            int val1 = stack1.isEmpty() ? 0 : stack1.pop();
            int val2 = stack2.isEmpty() ? 0 : stack2.pop();
            int sum = val1 + val2 + carry;
            carry = sum/10;
            ListNode node = new ListNode(sum%10);
            node.next = head;
            head = node;
        }
        return head;
    }
}

代码细节（不多，只有一个）

如果 当两个“栈”里数据拿完后，最后两个数据的和sum>10，即：carry 不为 0，，那么意味着需要为其在创造一个节点来存放carry的数据。这点跟它的前身题是一样的，