LeetCode: 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.

解答

人に見せるつもりのなかったクソコードで恥ずかしいのですが、、、 1番小さい桁から計算して順次ListNodeにしていくという方針です。

/**
 * 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 ans = null;
        ListNode current = null;
        boolean moveUp = false;
        while (true) {
            int val = 0;
            if (l1 != null) {
                val += l1.val;
            }
            if (l2 != null) {
                val += l2.val;
            }
            if (moveUp) {
                val += 1;
                moveUp = false;
            }
            if (val >= 10) {
                val -= 10;
                moveUp = true;
            }
            ListNode tmp = new ListNode(val);
            if (ans == null) {
                ans = tmp;
                current = tmp;
            } else {
                current.next = tmp;
                current = tmp;
            }
            if (l1 != null && l1.next != null) {
                l1 = l1.next;
            } else {
                l1 = null;
            }
            if (l2 != null && l2.next != null) {
                l2 = l2.next;
            } else {
                l2 = null;
            }
            if (l1 == null && l2 == null && !moveUp) {
                return ans;
            }
        }
    }
}

しかし、それでもやはり遅かった。。。

他の人の解答はというと、

/**
 * 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 first = null;
        ListNode last = null;
        int carry = 0;
        while (l1 != null || l2 != null || carry != 0) {
            int sum = 0;
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }
            sum += carry;
            
            ListNode newNode = new ListNode(sum % 10);
            if (last != null) {
                last.next = newNode;
                last = newNode;
            }
            last = newNode;
            if (first == null) {
                first = newNode;
            }
            
            carry = sum / 10;
        }
        return first;
    }
}

やっていることはほとんど同じだけど、if文がスッキリしていますね。 実行時間がそれぞれ35msと27msというように差が出たのですが、これはif比較の差なのかな？ これからも精進いたします。