力扣02 兩數相加
題目：
給你兩個 非空 的鏈表，表示兩個非負的整數，它們每位數字都是按照 逆序 的方式存盤的，并且每個節點只能存盤 一位 數字，
請你將兩個數相加，并以相同形式回傳一個表示和的鏈表，
你可以假設除了數字 0 之外，這兩個數都不會以 0 開頭，
示例：
2→ 4 →3
5 → 6 → 4
結果： 7 → 0 → 8
輸入：L1 = [2,4,3]
? L2 = [5,6,4]
輸出：L = [7,0,8]
注：因為4+6=10個位是0十位是1所以要向前進1
解法一： 迭代法
解題思路：
定義一個變數為total用來存盤兩個數字相加的和，定義一個變數為next1用來存盤total的十位上的數字也就是需要向前進的數字，可以先建立一個虛擬頭結點，這個虛擬頭結點指向真正的ListNode，這樣ListNode 不需要單獨處理，直接 while 回圈即可，
代碼：
/**
* 根據力扣的題目要求，求兩數之后并按要求回傳，
* 方法一：迭代法
*/
public class addTwoNumbers01 {
//1.定義一個方法回傳ListNode,方法引數為兩個鏈表ListNode l1 l2
public ListNode addTwoNumbers(ListNode l1,ListNode l2){
//1.1定義一個int型別的total用來存盤兩個數字的和,定義一個next1用來存盤 total/10 的值 就是要向前進的數
int total = 0;
int next1 = 0;
//1.2定義一個鏈表 用來存盤要回傳的數字
ListNode listNode = new ListNode();
//1.3定義一個curNode用來標記當前節點
ListNode curNode = listNode;
//2.1先回圈遍歷l1與l2長度相等的情況
while (l1 != null && l2 != null){
//2.2將l1的節點的值加上l2節點的值再加上next1賦值給total
total = l1.value + l2.value + next1;
//2.3取出total個位上的數字賦值給當前節點的下一個節點
curNode.next = new ListNode(total%10);
//2.4取出total上的十位數就是要向前進的數
next1 = total / 10;
//2.5分別將l1 l2 與當前節點向前移一位
l1 = l1.next;
l2 = l2.next;
curNode = curNode.next;
}
//3.1如果l1與l2長度不相等且l2先遍歷完
while (l1 != null){
//3.2將l1的值加上next1賦值給total
total = l1.value + next1;
curNode.next = new ListNode(total % 10);
next1 = total / 10;
l1 = l1.next;
curNode = curNode.next;
}
//4.1如果l2還沒遍歷完
while (l2 != null) {
total = l2.value + next1;
curNode.next = new ListNode(total % 10);
next1 = total / 10;
l2 = l2.next;
curNode = curNode.next;
}
//5.如果最后兩個鏈表都遍歷完之后還需要向前進位
if (next1 != 0){
curNode.next = new ListNode(next1);
}
return listNode.next;
}
}
注：
/ : 整除的結果是兩個數相除的整數部分不包括余數
% ：取余的結果是兩個數相除的余數部分不包括整數部分
示例： 10 / 7 = 1；10 % 7 = 3
解法二：遞回法
解題思路：
最重要的就是要保證兩個鏈表的長度相等，如果不相等我們也要想辦法把它們變成相等（添加零節點），
示例：
L1: 1 → 3 → 5 → 7 → 8 → 9
L2: 2 → 8 → 6 → 4 → 5
L ：3 → 1 → 2 → 2 → 4
L2下一節點為空了補上零節點:
L2： 2 → 8 → 6 → 4 → 5 → 0
L ： 3 → 1 → 2 → 2 → 4 → 0
根據規則還需要向前進1而L1,L2下一節點都為空所以都需要增加一個零節點
L1 ：1 → 3 → 5 → 7 → 8 → 9 → 0
L2 ：2 → 8 → 6 → 4 → 5 → 0 → 0
L ： 3 → 1 → 2 → 2 → 4 → 0 → 1
代碼：
/**
* 使用遞回法：每次保證兩個鏈表的長度一樣長，不一樣的給補成一樣長
*/
public class addTwoNumbers02 {
//1.定義一個方法回傳ListNode引數位ListNode l1,l2
public ListNode addTwoNumbers(ListNode l1,ListNode l2){
//2.定義兩個int型別的變數分別存盤兩數之和以及需要向前進位的數
int total = l1.value + l2.value;
int next1 = total / 10;
//2.1定義一個節點用來存放兩數之和各位上的數字
ListNode node = new ListNode(total % 10);
//3.保證兩個鏈表長度相等并且將next1的值與l1的值進行相加
if(l1.next != null || l2.next != null || next1 != 0){
//3.1如果l1或者l2下一個節點不為空就繼續向前走但凡有一個為空就新建一個0節點連接在后面
l1 = l1.next != null ? l1.next : new ListNode(0);
l2 = l2.next != null ? l2.next : new ListNode(0);
//3.2將next1的值與l1的值進行相加
l1.value += next1;
//3.3進行遞回
node.next = addTwoNumbers(l1, l2);
}
return node.next;
}
}
注： next1的不再是加在total上而是與L1.value相加，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/538951.html
標籤：其他