給你兩個(gè) 非空 的鏈表，表示兩個(gè)非負(fù)的整數(shù)。它們每位數(shù)字都是按照 逆序 的方式存儲(chǔ)的，并且每個(gè)節(jié)點(diǎn)只能存儲(chǔ) 一位 數(shù)字。

請(qǐng)你將兩個(gè)數(shù)相加，并以相同形式返回一個(gè)表示和的鏈表。

你可以假設(shè)除了數(shù)字 0 之外，這兩個(gè)數(shù)都不會(huì)以 0 開(kāi)頭。

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/add-two-numbers

示例：

image.png

輸入：l1 = [2,4,3], l2 = [5,6,4]
輸出：[7,0,8]
解釋?zhuān)?42 + 465 = 807.

輸入：l1 = [0], l2 = [0]
輸出：[0]

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

數(shù)據(jù)結(jié)構(gòu)

    class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

個(gè)人對(duì)于這種題目，就是簡(jiǎn)單的走一步看一步。可以從題目中看出，這其實(shí)就是簡(jiǎn)單版的大數(shù)相加，相加的結(jié)果需要有一個(gè)地方來(lái)存放，我首先想到的就是用一個(gè)List，然后將List的結(jié)果轉(zhuǎn)換為L(zhǎng)istNode,為什么不直接用ListNode作為結(jié)果呢？因?yàn)槟X子轉(zhuǎn)不過(guò)來(lái)，這是本人第一次看到這個(gè)題目所寫(xiě)：
思路：
1、先將兩數(shù)相同長(zhǎng)度的部分相加
2、對(duì)較長(zhǎng)數(shù)進(jìn)行進(jìn)位處理
3、對(duì)最后的進(jìn)位進(jìn)行處理
4、將結(jié)果集轉(zhuǎn)換為L(zhǎng)istNode

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int jinwei = 0;
        int result = 0;
        ListNode head = new ListNode();
        List<Integer> res = new ArrayList<>();
        // 兩數(shù)相加
        while(l1!=null && l2!=null){
            result = l1.val + l2.val + jinwei;
            jinwei = result / 10;
            res.add(result % 10);
            l1 = l1.next;
            l2 = l2.next;
        }
        // 兩個(gè)數(shù)中較大者與進(jìn)位相加
        while(l1!=null){
            res.add((l1.val + jinwei)%10);
            jinwei = (l1.val + jinwei) / 10; 
            l1 = l1.next;
        }

        while(l2!=null){
            res.add((l2.val + jinwei)%10);
            jinwei = (l2.val + jinwei) / 10; 
            l2 = l2.next;
        }
        // 最終還有進(jìn)位就裝進(jìn)結(jié)果集
        if(jinwei > 0){
            res.add(jinwei);
        }
        
        // 將結(jié)果集轉(zhuǎn)換為L(zhǎng)istNode
        ListNode current = head;
        for(int i=0 ; i < res.size(); i++){
            current.val = res.get(i);
            if(i!=res.size()-1){
                current.next = new ListNode();
                current = current.next;
            }
        }
        return head;
    }
}

分析上面的代碼，給人感覺(jué)重復(fù)代碼太多，而且不夠簡(jiǎn)潔，時(shí)間復(fù)雜度嘛O(n)還行，空間的話就蚌埠住了。看了官方解答之后，有一個(gè)點(diǎn)非常新奇，就是補(bǔ)"0"。位數(shù)不夠，0來(lái)湊，這也是大數(shù)相加的核心。。。
話不多說(shuō)，直接上代碼

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        // 創(chuàng)建一個(gè)操作指針
        ListNode current = head;
        int result = 0;
        int jinwei = 0;
        while( l1 != null || l2 != null) {
            int x = l1 == null ? 0 : l1.val;
            int y = l2 == null ? 0 : l2.val;

            result = x + y + jinwei;
            jinwei = result>9?1:0;
            result = result % 10;

            current.next = new ListNode(result);
            current = current.next;

            if(l1!=null){
                l1 = l1.next;
            }

            if(l2!=null){
                l2 = l2.next;
            }
        }

        if(jinwei>0){
            current.next = new ListNode(jinwei);
        }
        //head頭部為初始化的0，所以返回head.next
        return head.next;
    }
}

相比之前的方法，該方法將兩次循環(huán)合并(使用補(bǔ)"0"的方式，這樣的話，兩個(gè)ListNode就是一樣長(zhǎng)，就能將兩次循環(huán)合并)，并用ListNode來(lái)裝結(jié)果集。

image.png