【LeetCode】2.Add Two Numbers解題報告

転載は出典を明記してください.http://blog.csdn.net/crazy1235/article/details/52914703
Subject
出典:https://leetcode.com/problems/add-two-numbers/
You are given two linked lists representing two non-negative numbers.The digits are stored in reverse order and each of their nodes contain a single digit.Add the two numbers and return it it.
Input:(2->4->3)+(5->6->4)Output:7->0->8
エクスプレーン
2つのチェーンがあります.逆順の2つの非負数を表します.2つの数の和を計算した後、同じ逆順出力をチェーンとして出力します.
注意してください.進数があります.
Solution
ソロ1
二つのチェーンを便利にして、これによって足し算して、進数の数字を次のグループの加算数に含めます.
注意したいのは、{5}、{5}の2つのリストで、出力の結果は{0,1}であるべきです.

/**
     * 57ms 

     *             0
     * 
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return null;
        }
        ListNode temp = new ListNode(0);
        ListNode result = temp;

        int value1 = 0;
        int value2 = 0;
        while (l1 != null && l2 != null) {
            value2 = (l1.val + l2.val + value1) % 10;
            value1 = (l1.val + l2.val + value1) / 10;

            temp.next = new ListNode(value2);
            l1 = l1.next;
            l2 = l2.next;
            temp = temp.next;
            if (l1 == null && l2 == null) {
                break;
            }
            if (l1 == null) {
                l1 = new ListNode(0);
            }
            if (l2 == null) {
                l2 = new ListNode(0);
            }
        }
        if (value1 != 0) {
            temp.next = new ListNode(value1);
        }
        return result.next;
    }

solution 2
再帰的方式

/**
     *      -- 56ms
     * 
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return l1 == null ? l2 : l1;
        }
        int value = l1.val + l2.val;
        ListNode result = new ListNode(value % 10);
        result.next = addTwoNumbers2(l1.next, l2.next);
        if (value >= 10) {
            result.next = addTwoNumbers2(new ListNode(value / 10), result.next);
        }
        return result;
    }

ソロ3
『九章アルゴリズム』の答えから.
過程を三つの状況に分けます.二つのチェーンなどの長さに対応する数字の和を計算して、二つのチェーンが空いています.この場合は2つの場合(類似の場合)があります.l 1が空でない場合は、l 1チェーンの値を「キャリー」と加算して、次の結果要素の値とします.

/**
     *        

     * http://www.jiuzhang.com/solutions/add-two-numbers/
     * 
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers3(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) {
            return null;
        }

        ListNode head = new ListNode(0);
        ListNode point = head;
        int carry = 0;
        while (l1 != null && l2 != null) {
            int sum = carry + l1.val + l2.val;
            point.next = new ListNode(sum % 10);
            carry = sum / 10;
            l1 = l1.next;
            l2 = l2.next;
            point = point.next;
        }

        while (l1 != null) {
            int sum = carry + l1.val;
            point.next = new ListNode(sum % 10);
            carry = sum / 10;
            l1 = l1.next;
            point = point.next;
        }

        while (l2 != null) {
            int sum = carry + l2.val;
            point.next = new ListNode(sum % 10);
            carry = sum / 10;
            l2 = l2.next;
            point = point.next;
        }

        if (carry != 0) {
            point.next = new ListNode(carry);
        }
        return head.next;
    }

ビンゴ~