LeetCode Note Java 00002：Add Two Numbers

輸入兩個非空的 linked list，分別表示兩個非負的整數，一個 node 包含一個數字，並且是反向排列 (第一個數字是個位數)，回傳兩數字相加的 linked list 結果。

題目

Add Two Numbers Medium

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 contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

我的解法

/**
 * 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 Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode l3 = new ListNode(0);
        ListNode l1tmp = l1, l2tmp = l2, l3tmp = l3;
        while (l1tmp != null || l2tmp != null || l3tmp != null) {
            if (l1tmp == null) {
                l1tmp = new ListNode(0);
            }
            if (l2tmp == null) {
                l2tmp = new ListNode(0);
            }
            l3tmp.val += ((l1tmp == null ? 0 : l1tmp.val) + (l2tmp == null ? 0 : l2tmp.val));
            if (l3tmp.val >= 10) {
                l3tmp.val -= 10;
                l3tmp.next = new ListNode(1);
            } else {
                if (l1tmp.next != null || l2tmp.next != null) {
                    l3tmp.next = new ListNode(0);
                }
            }
            if (l1tmp != null) {
                l1tmp = l1tmp.next;
            }
            if (l2tmp != null) {
                l2tmp = l2tmp.next;
            }
            l3tmp = l3tmp.next;
        }
        return l3;
    }
}

注意

• 需要了解 Linked List 基本原理，要一直用 next 相關聯。

• 輸出的 ListNode 可能因為進位而比輸入的 ListNode 長。

• 沒處理好會很容易發生 NullPointer Exception。

檢討

別人的解法解題思路沒有差很多，但 code 比我簡潔很多，所以我可以再減少變數的使用。

[Java concise solution.]](https://leetcode.com/problems/add-two-numbers/solutions/1044/java-concise-solution/)

重新整理 code：

/**
 * 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 Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode l3head = new ListNode(); // 只是個假頭，方便後面造 next 的邏輯
        ListNode l3tmp = l3head;
        while (l1 != null || l2 != null || l3tmp.next != null) {
            if (l3tmp.next == null) {
                l3tmp.next = new ListNode(0); // 為了避免產出多餘的尾巴，在迴圈開頭才造出 next
            }
            l3tmp = l3tmp.next;
            l3tmp.val += ((l1 != null ? l1.val : 0) + (l2 != null ? l2.val : 0));
            if (l3tmp.val >= 10) {
                l3tmp.val -= 10;
                l3tmp.next = new ListNode(1);
            }
            l1 = l1 != null ? l1.next : null;
            l2 = l2 != null ? l2.next : null;
        }
        return l3head.next; // 因為前面有個假頭，所以是回傳 next
    }
}