前言

今天無意間看到LeetCode的一道“兩數相加”的算法題，第一次接觸鏈表ListNode，ListNode結構如下：

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;}}

算法題目

給你兩個?非空?的鏈表，表示兩個非負的整數。它們每位數字都是按照?逆序?的方式存儲的，并且每個節點只能存儲?一位?數字。

請你將兩個數相加，并以相同形式返回一個表示和的鏈表。

你可以假設除了數字 0 之外，這兩個數都不會以 0?開頭。

示例 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]

提示：

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

解題思路

使用迭代的方法來實現鏈表的相加。從兩個鏈表的頭節點開始，依次將對應位置的數字相加，并保留進位。在遍歷完兩個鏈表的所有節點之后，如果還存在進位，就需要在結果鏈表中追加一個節點來存儲進位。

第一版代碼

/*** 兩數相加*/public ListNode addTwoNumbers(ListNode l1, ListNode l2) {StringBuilder s = new StringBuilder();while (l1 != null) {s.append(l1.val);l1 = l1.next;}StringBuilder s1 = new StringBuilder();for (int i = s.toString().length(); i > 0; i--) {s1.append(s.toString().charAt(i - 1));}long x1 = Long.parseLong(s1.toString());s = new StringBuilder();while (l2 != null) {s.append(l2.val);l2 = l2.next;}s1 = new StringBuilder();for (int i = s.toString().length(); i > 0; i--) {s1.append(s.toString().charAt(i - 1));}long x2 = Long.parseLong(s1.toString());long sum = x1 + x2;//結果倒序s1 = new StringBuilder();for (int i = String.valueOf(sum).length(); i > 0; i--) {s1.append(String.valueOf(sum).charAt(i - 1));}//返回鏈表ListNode listNode = new ListNode(Integer.parseInt(s1.substring(0, 1)));ListNode p = listNode;//聲明一個變量在移動過程中充當節點for (int i = 1; i < s1.toString().length(); i++) {p.next = new ListNode(Integer.parseInt(s1.substring(i, i + 1)));    //創建鏈表的下一個節點，并賦值p = p.next;    //將指針的位置指向當前節點}return listNode;}

注意：萬萬沒有想到，在LeetCode通過測試，但是提交的時候，卻被一個長鏈表被給卡主了，查看了錯誤，發現是超出了long的長度，不能用傳統的方法來解決，只能通過每一位數的相加，然后進位進行循環計算和進位處理。

經過思考和優化，最后優化代碼如下，順利提交LeetCode通過所有的測試用例。

最終實現代碼

/*** 兩數相加*/public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode ln = l1;ListNode lx = l2;StringBuilder res = new StringBuilder();int val = 0;while (ln != null || lx != null) {int x = (ln != null) ? ln.val : 0;int y = (lx != null) ? lx.val : 0;int sum = x + y + val;if (sum >= 10) {//大于10res.append(sum % 10);//下一次運算+Nval = sum / 10;} else {//小于10res.append(sum);//清空進位val = 0;}//下一個ln = ln != null ? ln.next : null;lx = lx != null ? lx.next : null;}if (val > 0) {//結果有進位res.append(val);}//返回鏈表ListNode listNode = new ListNode(Integer.parseInt(res.substring(0, 1)));ListNode p = listNode;//聲明一個變量在移動過程中充當節點for (int i = 1; i < res.toString().length(); i++) {p.next = new ListNode(Integer.parseInt(res.substring(i, i + 1)));//創建鏈表的下一個節點，并賦值p = p.next;    //將指針的位置指向當前節點}return listNode;}

📚學習永無止境，每天進步一點點，向知識的海洋更深處探索。