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

給你兩個(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)頭。

示例 1：

輸入：l1 = [2,4,3], l2 = [5,6,4]
輸出：[7,0,8]
解釋：342 + 465 = 807.

示例 2：

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

示例 3：

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

提示：

• 每個(gè)鏈表中的節(jié)點(diǎn)數(shù)在范圍 [1, 100] 內(nèi)
• 0 <= Node.val <= 9
• 題目數(shù)據(jù)保證列表表示的數(shù)字不含前導(dǎo)零

解法一：

根據(jù)鏈表特點(diǎn)，直接按順序遍歷，計(jì)算對(duì)應(yīng)位的數(shù)值，同時(shí)記錄進(jìn)位即可。

public class Add {public static void main(String[] args) {Add add = new Add();ListNode l1 = new ListNode(1);l1.next = new ListNode(2);ListNode l2 = new ListNode(9);l2.next = new ListNode(8); // l2.next.next = new ListNode(4);ListNode listNode = add.addTwoNumbers2(l1, l2);System.out.println(listNode);}public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {// 定義當(dāng)前遍歷到的節(jié)點(diǎn)--可以省略，直接使用l1和l2ListNode cur1 = l1;ListNode cur2 = l2;// 結(jié)果：待返回的nodeListNode node = null;// 處理返回鏈表中，當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)ListNode next = null;// 相加后進(jìn)位數(shù)值：8+3=11，則進(jìn)位1int step = 0;// 這里遍歷次數(shù)執(zhí)行定義為1000，因?yàn)闂l件中說(shuō)明，數(shù)值最大不超過(guò)100位，也就是鏈表長(zhǎng)度不可能超過(guò)100.// 這里可以優(yōu)化，使用while循環(huán)，將下面的退出條件放在while條件中for (int i = 0; i < 1000; i++) {// 當(dāng)前節(jié)點(diǎn)數(shù)值int val1 = 0;int val2 = 0;if (cur1 != null) {val1 = cur1.val;cur1 = cur1.next;}if (cur2 != null) {val2 = cur2.val;cur2 = cur2.next;}// 當(dāng)前節(jié)點(diǎn)值加進(jìn)位的數(shù)值之和int val = val1 + val2 + step;// 處理進(jìn)位以及計(jì)算當(dāng)前位置最終值step = val / 10;val = val - step * 10;if (node == null) {node = new ListNode(val);// 記錄next，方便給下一個(gè)節(jié)點(diǎn)關(guān)聯(lián)next = node;} else {next.next = new ListNode(val);next = next.next;}// 如果當(dāng)前節(jié)點(diǎn)都為空，且沒(méi)有進(jìn)位，則停止if (cur1 == null && cur2 == null && step==0) {break;}}return node;}}class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) {this.val = val;}ListNode(int val, ListNode next) {this.val = val;this.next = next;} }

解法二：遞歸

遞歸退出條件：當(dāng)兩個(gè)節(jié)點(diǎn)都是空的時(shí)候退出。
那如果有任一節(jié)點(diǎn)為空，另外一個(gè)節(jié)點(diǎn)不為空，那我們的節(jié)點(diǎn)相加邏輯就會(huì)出現(xiàn)空指針異常，在這里直接犧牲空間來(lái)滿足處理邏輯。
進(jìn)位處理：默認(rèn)在任何一個(gè)加數(shù)節(jié)點(diǎn)上即可，這里放在了l1上

/*** 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) {if(l1 == null && l2 ==null){return null;}if(l1 == null){l1 = new ListNode(0);}if(l2 == null){l2 = new ListNode(0);}int rval = l1.val + l2.val;if(rval >= 10){rval = rval % 10;if(l1.next != null){l1.next.val+=1;}else{l1.next = new ListNode(1);}}return new ListNode(rval, addTwoNumbers(l1.next, l2.next));} }

總結(jié)

以上是生活随笔為你收集整理的【LeetCode每周算法】两数相加的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。