給你兩個 非空 的鏈表登刺，表示兩個非負的整數(shù)籽腕。它們每位數(shù)字都是按照 逆序 的方式存儲的，并且每個節(jié)點只能存儲 一位 數(shù)字纸俭。
請你將兩個數(shù)相加皇耗，并以相同形式返回一個表示和的鏈表。
你可以假設除了數(shù)字 0 之外揍很，這兩個數(shù)都不會以 0 開頭郎楼。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/add-two-numbers
示例：
輸入：l1 = [2,4,3], l2 = [5,6,4]
輸出：[7,0,8]
解釋：342 + 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ù)結構
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ù)相加简珠，相加的結果需要有一個地方來存放阶界，我首先想到的就是用一個List，然后將List的結果轉(zhuǎn)換為ListNode,為什么不直接用ListNode作為結果呢北救？因為腦子轉(zhuǎn)不過來荐操，這是本人第一次看到這個題目所寫：
思路：
1、先將兩數(shù)相同長度的部分相加
2珍策、對較長數(shù)進行進位處理
3、對最后的進位進行處理
4宅倒、將結果集轉(zhuǎn)換為ListNode
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;
}
// 兩個數(shù)中較大者與進位相加
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;
}
// 最終還有進位就裝進結果集
if(jinwei > 0){
res.add(jinwei);
}
// 將結果集轉(zhuǎn)換為ListNode
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;
}
}
分析上面的代碼攘宙，給人感覺重復代碼太多，而且不夠簡潔，時間復雜度嘛O(n)還行蹭劈，空間的話就蚌埠住了疗绣。看了官方解答之后铺韧，有一個點非常新奇多矮，就是補"0"。位數(shù)不夠哈打，0來湊塔逃，這也是大數(shù)相加的核心。料仗。湾盗。
話不多說，直接上代碼
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = new ListNode(0);
// 創(chuàng)建一個操作指針
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)合并(使用補"0"的方式，這樣的話氛改，兩個ListNode就是一樣長帐萎，就能將兩次循環(huán)合并)，并用ListNode來裝結果集胜卤。
