Java如何實(shí)現(xiàn)兩數(shù)相加

發(fā)布時間：2022-01-17 11:41:10 來源：億速云閱讀：253 作者：小新欄目：大數(shù)據(jù)

這篇文章主要為大家展示了“Java如何實(shí)現(xiàn)兩數(shù)相加”，內(nèi)容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領(lǐng)大家一起研究并學(xué)習(xí)一下“Java如何實(shí)現(xiàn)兩數(shù)相加”這篇文章吧。

題目描述

給出兩個非空的鏈表用來表示兩個非負(fù)的整數(shù)。其中，它們各自的位數(shù)是按照逆序的方式存儲的，并且它們的每個節(jié)點(diǎn)只能存儲一位數(shù)字。

如果，我們將這兩個數(shù)相加起來，則會返回一個新的鏈表來表示它們的和。

您可以假設(shè)除了數(shù)字 0 之外，這兩個數(shù)都不會以 0 開頭。

示例：

輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)輸出：7 -> 0 -> 8原因：342 + 465 = 807

解題方案

思路

標(biāo)簽：鏈表
將兩個鏈表看成是相同長度的進(jìn)行遍歷，如果一個鏈表較短則在前面補(bǔ)0，比如 987 + 23 = 987 + 023 = 1010
每一位計算的同時需要考慮上一位的進(jìn)位問題，而當(dāng)前位計算結(jié)束后同樣需要更新進(jìn)位值
如果兩個鏈表全部遍歷完畢后，進(jìn)位值為1，則在新鏈表最前方添加節(jié)點(diǎn)1
小技巧：對于鏈表問題，返回結(jié)果為頭結(jié)點(diǎn)時，通常需要先初始化一個預(yù)先指針pre，該指針的下一個節(jié)點(diǎn)指向真正的頭結(jié)點(diǎn)head。使用預(yù)先指針的目的在于鏈表初始化時無可用節(jié)點(diǎn)值，而且鏈表構(gòu)造過程需要指針移動，進(jìn)而會導(dǎo)致頭指針丟失，無法返回結(jié)果。

代碼

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */class Solution {    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {        ListNode pre = new ListNode(0);        ListNode cur = pre;        int carry = 0;        while(l1 != null || l2 != null) {            int x = l1 == null ? 0 : l1.val;            int y = l2 == null ? 0 : l2.val;            int sum = x + y + carry;                        carry = sum / 10;            sum = sum % 10;            cur.next = new ListNode(sum);
            cur = cur.next;            if(l1 != null)                l1 = l1.next;            if(l2 != null)                l2 = l2.next;        }        if(carry == 1) {            cur.next = new ListNode(carry);        }        return pre.next;    }}