兩數(shù)相加的實現(xiàn)方法有哪些

這篇文章主要介紹“兩數(shù)相加的實現(xiàn)方法有哪些”，在日常操作中，相信很多人在兩數(shù)相加的實現(xiàn)方法有哪些問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”兩數(shù)相加的實現(xiàn)方法有哪些”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

“兩數(shù)相加”

先來看題目描述

給你兩個非空的鏈表，表示兩個非負的整數(shù)。它們每位數(shù)字都是按照逆序的方式存儲的，并且每個節(jié)點只能存儲一位數(shù)字。請你將兩個數(shù)相加，并以相同形式返回一個表示和的鏈表。你可以假設(shè)除了數(shù)字0之外，這兩個數(shù)都不會以0開頭。

兩數(shù)相加

鏈表節(jié)點的數(shù)據(jù)結(jié)構(gòu)如下：

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; }  }

題目說明

題目描述相對來說比較繞，我們可以直接理解為兩個多位的整數(shù)相加，只不過整數(shù)的每一位都是通過鏈表進行存儲。比如，整數(shù)342，通過鏈表存儲正常來說應(yīng)該是3->4->2，但是計算時，往往需要從低位開始計算，逢十進一，所以題目中直接將整數(shù)表示為2->4->3，這樣反而不用將鏈表順序進行反轉(zhuǎn)了，直接相加就可以了。

兩數(shù)相加

需要注意的是如果兩個鏈表的長度不同，則可以認為長度短的鏈表的后面有若干個 0  ，鏈表遍歷結(jié)束，則如果進位值大于0，則還需要在結(jié)果鏈表中附加一個值為1的節(jié)點。

方法一：模擬

上面已經(jīng)提到，鏈表是逆序的，因此直接對應(yīng)數(shù)字相加即可。基本操作遍歷兩個列表，逐位計算它們的和，并與當前位置的進位值相加。

比如，兩個鏈表對應(yīng)位的數(shù)字分別為n1和n2，進位為carry(通常為0和1)，則它們的和為(n1 + n2 + carry)，對應(yīng)位上數(shù)字變?yōu)?n1 +  n2 + carry)%10，新的進位為(n1 + n2 + carry)/10。

如果兩個鏈表長度不一樣，長度短的鏈表后續(xù)對應(yīng)位上值均為0即可。如果遍歷結(jié)束之后，carray大于0(也就是等于1)，則在結(jié)構(gòu)鏈表后面新增一個節(jié)點，

實現(xiàn)代碼如下：

class Solution {     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {         ListNode head = null, tail = null;         int carry = 0;         while (l1 != null || l2 != null) {             int n1 = l1 != null ? l1.val : 0;             int n2 = l2 != null ? l2.val : 0;             int sum = n1 + n2 + carry;             if (head == null) {                 head = tail = new ListNode(sum % 10);             } else {                 tail.next = new ListNode(sum % 10);                 tail = tail.next;             }             carry = sum / 10;             if (l1 != null) {                 l1 = l1.next;             }             if (l2 != null) {                 l2 = l2.next;             }         }         if (carry > 0) {             tail.next = new ListNode(carry);         }         return head;     } }

上述方法時間復(fù)雜度的計算與鏈表的長度有關(guān)，比如兩個鏈表的長度分別為m和n，則遍歷的次數(shù)為max(m,n)，也就m和n中取最大值，所以時間復(fù)雜度為O(n)。

由于要對鏈表的每一位進行計算存儲，并且最后如果有進位，還要多加一位，因此最長鏈表為max(m,n)+1，所以空間復(fù)雜度為O(n);

通過思路分析，寫出上面的代碼還是比較容易的。但這個題目是否可以考慮用遞歸的形式來解決呢?我們來看看方法二。

方法二：遞歸

第一種方法很簡單，按照正常的思維邏輯來就可以了。但評論區(qū)有這樣一句話“不用遞歸沒有靈魂。盡管多數(shù)時候，遞歸不見得更有效率。”那么我們就來看看用遞歸的形式如何實現(xiàn)。

class Solution {     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {         return add(l1,l2,0);     }     public ListNode add(ListNode l1, ListNode l2, int carry){         if(l1 == null && l2 == null && carry == 0) return null;         int x = l1==null ? 0 : l1.val;         int y = l2==null ? 0 : l2.val;         int sum = x + y + carry;         ListNode n = new ListNode(sum % 10);         n.next = add(l1==null ? null : l1.next,                      l2==null ? null : l2.next,                      sum/10);         return n;      } }

上述代碼的基本迭代邏輯循環(huán)如下：

兩數(shù)相加

通過上圖我們可以推演一下遞歸調(diào)用的時間復(fù)雜度。針對遞歸調(diào)用的時間復(fù)雜度計算，本質(zhì)上要看：遞歸的次數(shù)??每次遞歸中的操作次數(shù)。那么，上述方法遞歸了幾次呢?遞歸的次數(shù)也是與兩個鏈表最長的那個的長度有關(guān)，最后可能會因為進位多算一次，因此遞歸次數(shù)為n或n+1，而內(nèi)部計算并不隨n的變化而變化，執(zhí)行次數(shù)為常數(shù)。因此整體時間復(fù)雜度為n*1  = O(n)。

空間復(fù)雜度依舊與結(jié)果鏈表的長度有關(guān)，因此依舊為O(n)。

到此，關(guān)于“兩數(shù)相加的實現(xiàn)方法有哪些”的學習就結(jié)束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續(xù)學習更多相關(guān)知識，請繼續(xù)關(guān)注億速云網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>