?LeetCode(數學分類) 2. 兩數相加——暴力與優化?

提示：
每個鏈表中的節點數在范圍 [1, 100] 內
0 <= Node.val <= 9
題目數據保證列表表示的數字不含前導零

題解：

暴力與優化，暴力即轉換為十進制解題，優化即直接在鏈表上進行操作，模擬十進制即可進行進位；

代碼：

/*** 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 Solution1 {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode res = new ListNode();// 不用long時由于鏈表長度可達100會超int 但long依舊超限制long n1 = 0;  long n2 = 0;long stand = 1;while(l1 != null){long tmp = l1.val * stand;n1 += tmp;stand *= 10;l1 = l1.next;}stand = 1;while(l2 != null){long tmp = l2.val * stand;n2 += tmp;stand *= 10;l2 = l2.next;}long n = n1 + n2;if(n == 0){res.val = 0;return res;}ListNode head = res;while(n > 0){int tt = (int)(n % 10);ListNode tmp = new ListNode(tt);head.next = tmp;head = head.next;n /= 10;}return res.next;}
}// 最優解 直接在鏈表上模擬十進制運算進行加法及進位操作 
// 難點在于模擬過程需要對進位進行合理處理
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {// 保存最終鏈表頭部的指針ListNode res = new ListNode();// 用于幫助構建res的遍歷指針ListNode head = res;// 暫存器 用于l1和l2后面均為null時若前一節點有需要進位的1時則置為一 無該情況默認0int extra = 0;// 標志位 用于標志哪一個鏈表在退出第一個while后還有多余未遍歷的節點boolean f1 = false;boolean f2 = false;// 采用雙指針統一遍歷 模擬十進制加法 遇到進位需額外處理 直到某一鏈表遍歷完全或均遍歷完全則退出模擬while(l1 != null && l2 != null){int n1 = l1.val;int n2 = l2.val;int n = n1 + n2;// 發生進位if(n >= 10){int tmp = n % 10;// 及時進1給高位 若l1后不空可進位到l1下一點 若空進到l2下一點// 若后面均空則進位到暫存器extraif(l1.next != null)l1.next.val++;else if(l2.next != null)l2.next.val++;else    extra = 1;ListNode tNode = new ListNode(tmp);head.next = tNode;}// 未進位 直接新增和的節點else{ListNode tNode = new ListNode(n);head.next = tNode;}// head記得要移動head = head.next;// 越界判斷 方便while模擬加法過程退出后哪一鏈表會剩余節點if(l1.next == null && l2.next == null){f1 = true;f2 = true;}else if(l1.next == null){f1 = true;}else if(l2.next == null){f2 = true;}// 固定移動l1 = l1.next;l2 = l2.next;}// 不可直接將余下的直接鏈接 因可能存在低位向不為null的節點高位+1情況 會導致9->10 故要檢查// eg： l1 = [9,9,9,9,9,9,9] l2 = [9,9,9,9] // 不加額外操作輸出 [8,9,9,9,10,9,9]// 正確為 [8,9,9,9,0,0,0,1]if(f1 && !f2){if(l2.val == 10){// 標志位 標志l2余下鏈表是否有東西boolean flag = false;// 若出現上述預測情況 則要進行循環判斷 因可能后1進到前1導致前由9->10 故要繼續進位while(l2.val == 10){ListNode tNode = new ListNode(0);head.next = tNode;head = head.next;// 后有東西直接進位+1if(l2.next != null){l2 = l2.next;l2.val++;}// 后無東西則創建一新節點即可 同時l2代表遍歷完全else{ListNode tmpNode = new ListNode(1);head.next = tmpNode;flag = true;break;}}// 直至余下鏈表中無10 此時可直接鏈接if(!flag)head.next = l2;}// 無10 可直接鏈接else{head.next = l2;}}// 同上else if(!f1 && f2){if(l1.val == 10){// 標志位 標志余下鏈表是否有東西boolean flag = false;// 若出現上述預測情況 則要進行循環判斷 因可能后1進到前1導致前由9->10 故要繼續進位while(l1.val == 10){ListNode tNode = new ListNode(0);head.next = tNode;head = head.next;// 后有東西直接進位+1if(l1.next != null){l1 = l1.next;l1.val++;}// 后無東西則創建一新節點即可 同時l1代表遍歷完全else{ListNode tmpNode = new ListNode(1);head.next = tmpNode;flag = true;break;}}// 直至余下鏈表中無10 此時可直接鏈接if(!flag)head.next = l1;}// 無10 可直接鏈接else{head.next = l1;}}// 此不存在上述情況 但可能存在extra 故要考慮是否要因進位而多增加一個節點 其val=1else if(f1 && f2){if(extra == 1){ListNode tNode = new ListNode(1);head.next = tNode;}}// res為帶頭節點的鏈表 故返回其nextreturn res.next;}
}

結果：