兩數相加（Add Two Numbers）
題目
英文
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)Output: 7 -> 0 -> 8Explanation: 342 + 465 = 807.
中文
給出兩個 非空 的連結串列用來表示兩個非負的整數。其中，它們各自的位數是按照 逆序 的方式儲存的，並且它們的每個節點只能儲存 一位 數字。
如果，我們將這兩個數相加起來，則會返回一個新的連結串列來表示它們的和。
您可以假設除了數字 0 之外，這兩個數都不會以 0 開頭。
示例：
輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807
解答
按照一般的加法規則計算，從低位往高位進行計算，如果某一位計算超過10就進一（當前為取餘），當高位沒有的時候，就補0即可。這裡已經是逆序排列來，那麼直接迴圈進行計算
Java
case1
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode result = null;
//上一個節點資料的臨時保持，方便添加當前節點的結果
ListNode lastNode = null;
// 判斷上一個節點計算結果是否有進位
boolean lastNodeHasStepIn = false;
// 按照加法的計算，同步進位即可，
while (l1 != null || l2 != null) {
int curVal = (l1 != null ? l1.val : 0) + (l2 != null ? l2.val : 0);
// 低位是否有進位
if (lastNodeHasStepIn) {
curVal += 1;
lastNodeHasStepIn = false;
}
//判斷是否存在進位
if (curVal >= 10) {
curVal = curVal % 10;
lastNodeHasStepIn = true;
}
ListNode currentNode = new ListNode(curVal);
//todo 可以節省這一步，提升時間效率
if (result == null) {
result = currentNode;
} else {
lastNode.next = currentNode;
}
// 切換Node
lastNode = currentNode;
l1 = l1 == null ? null : l1.next;
l2 = l2 == null ? null : l2.next;
}
if (lastNodeHasStepIn) {
ListNode next = new ListNode(1);
result.next = next;
}
return result;
}
}
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
結論： 接受
時間：2 ms（96.54%）
記憶體：45.8 MB（ 56.11%）
分析
上面的演算法中，lastNodeHasStepIn 不斷判斷會增加時間，其中對result == null
的每一步判斷實際上不需要，同樣增加了時間，其實只是第一步的時候需要。那麼可以進行優化如下：
/**
* Definition for singly-linked list.
* public class ListNode {
*int val;
*ListNode next;
*ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode result = new ListNode(-1);
//上一個節點資料的臨時保持，方便添加當前節點的結果
ListNode lastNode = result;
// 上一步的進位為0；預設沒有
int stepIn = 0;
// 按照加法的計算，同步進位即可，
while (l1 != null || l2 != null) {
// 兩數同位之後，加上低位的步進
int curVal = (l1 != null ? l1.val : 0)
+ (l2 != null ? l2.val : 0)
+ stepIn;
//計算是否有步進，強制取整
stepIn = curVal / 10;
// 取餘獲得數值，如果有步進的話
curVal = curVal % 10;
lastNode.next = new ListNode(curVal);
// 切換Node
lastNode = lastNode.next;
l1 = l1 == null ? null : l1.next;
l2 = l2 == null ? null : l2.next;
}
if (stepIn > 0) {
lastNode.next = new ListNode(stepIn);
}
return result.next;
}
}
結論： 接受
時間：2 ms（96.54%）
記憶體：45 MB（ 61.38% ）
好吧時間居然沒有減少，倒是記憶體少了，感覺判斷條件對最終結果影響不大，所以我最終改成了如下：
/**
* Definition for singly-linked list.
* public class ListNode {
*int val;
*ListNode next;
*ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode result = null;
ListNode lastNode = null;
int stepIn = 0;
while (l1 != null || l2 != null) {
int curVal = (l1 != null ? l1.val : 0)
+ (l2 != null ? l2.val : 0)
+ stepIn;
stepIn = curVal / 10;
curVal = curVal % 10;
ListNode curNode = new ListNode(curVal);
if (result != null) {
lastNode.next = curNode;
} else {
result = curNode;
}
lastNode = curNode;
l1 = l1 == null ? null : l1.next;
l2 = l2 == null ? null : l2.next;
}
if (stepIn > 0) {
lastNode.next = new ListNode(stepIn);
}
return result;
}
}