Leetcode 2

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 as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8
なお、ここでの演算は実際には342+465=807である.注意チェーンテーブルはここで数字が逆であることを示しています.
Solution1

は、合計が反復のたびに実際には3つの数が加算されることを考慮し、2つはそれぞれ2つのチェーンテーブルの数であり、もう1つはキャリーの数である.この3つの数字はそれぞれ8種類の0でない組み合わせがあり、以下に示す:

チェーンテーブル1
チェーンテーブル2
キャリフラグci
処理状況
1
1
1
せいじょうしょり
1
1
0
せいじょうしょり
1
0
1
せいじょうしょり
0
1
1
せいじょうしょり
1
0
0
ジャンプサイクル
0
1
0
ジャンプサイクル
0
0
1
せいじょうしょり
0
0
0
ジャンプサイクル
上記の考えをコードに以下のように表現します.

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode node = dummy;
        int ci = 0;
        while(ci!=0||(l1!=null&&l2!=null)){
            int temp = ci;
            if(l1!=null){
                temp += l1.val;
                l1 = l1.next;
            }
            if(l2!=null){
                temp += l2.val;
                l2 = l2.next;
            }
            node.next = new ListNode(temp%10);
            node = node.next;
            ci = temp/10;
        }
        node.next = (l1!=null?l1:l2);//                ，            。
        return dummy.next;
    }
}

上記の方法は反復の思想を用いて、再帰を用いていないし、論理も非常にはっきりしていて、このようにいくつかの変数のすべての組み合わせの状況をすべて列挙して、それからその中のいくつかを合併処理して、多くのプログラムがすべての状況を列挙して考慮する必要がある時特によく見られて、把握する価値があります.
Solution2

では、この問題を再帰的に解決する方法について説明します.

まず、この問題を再帰的に解くことができる理由を見てみましょう.各チェーンテーブルの最初の数字2+5=7を考察すると、結果を表す新しいチェーンテーブルの前の合計された前のノードがこの新しいノードを指します.この時、残りの問題は元の問題と同じ問題であることに気づいたが、規模が小さくなっただけだ.これは再帰的な典型的な過程である.

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode prev = dummy;
        help(l1,l2,prev,0);
        return dummy.next;
    }
    public void help(ListNode l1,ListNode l2,ListNode prev,int ci){
        if(ci!=0||(l1!=null&&l2!=null)){
            int temp = ci;
            if(l1!=null){
                temp += l1.val;
                l1 = l1.next;
            }
            if(l2!=null){
                temp += l2.val;
                l2 = l2.next;
            }
            prev.next = new ListNode(temp%10);
            help(l1,l2,prev.next,temp/10);
        }else prev.next = (l1!=null?l1:l2);
    }
}

ここでは実際に反復に基づく解法と変わらない.この問題を説明するために再帰的な解法で解くことができるだけだ.
Solution3

実際にはnullを0とし,解法1の3つの変数がすべて0になるまでループを停止する考え方もある.これで考察の状況はさらに少なくなった.コードは次のとおりです:

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode prev = dummy;
        int ci = 0;
        while(ci!=0||l1!=null||l2!=null){//                
            int temp = ci + (l1!=null?l1.val:0) + (l2!=null?l2.val:0);// null  0   
            prev.next = new ListNode(temp%10);
            ci = temp/10;
            prev = prev.next;
            l1 = (l1!=null?l1.next:null);//  l1   ，        。    ，   
            l2 = (l2!=null?l2.next:null);
        }
        return dummy.next;
    }
}