文章目錄

前身
題目
題目決議
解題程序
- 首先我們為題目的兩個鏈表，各自創建一個堆疊，
- 然后便是將 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，我們這題就算完成了！

代碼如下

/**
 * Definition for singly-linked list.
 * 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) {
        Deque<Integer> stack1 = new LinkedList<>();
        Deque<Integer> 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;
    }
}