Leetcode問題解-チェーンテーブル-(7)-チェーンテーブルの合計

[LeetCode]Add Two Numbers IIの2つの数字を加算する2
 
You are given two linked lists representing two non-negative numbers. The most significant digit comes first 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.
Follow up:What if you cannot modify the input lists? In other words, reversing the lists is not allowed.
Example:
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7
チェーンテーブルをひっくり返すとスタックと再帰の2種類があると思います
この問題は以前のAdd Two Numbersの拡張であり、この問題の最高位がチェーンテーブルの先頭にあることを見ることができ、チェーンテーブルを反転させると前の問題と同じになります.ここではチェーンテーブルの順序を変更しない方法を見てみましょう.加算には最低位から演算を開始する必要があるため、最低位はチェーンテーブルの末尾にあり、チェーンテーブルは行き先から遍歴するしかなく、前の要素を取ることができません.どうすればいいですか?スタックを使用してすべての要素を保存し、スタックの後進先出の特徴を利用して後から数字を取ることができます.私たちはまず2つのチェーンテーブルを巡り、すべての数字を2つのスタックs 1とs 2にそれぞれ押し込み、0のresノードを確立し、ループを開始します.スタックが空でなければ、スタックのトップ数字をsumに追加します.次にresノード値をsum%10に割り当て、次にsum/10に割り当てるキャリーノードheadを新規作成します.キャリーがなければ0です.その後、headにresを接続し、resをheadに指します.このようにループが終了すると、resの値が0であるかどうかを見て、0であるかどうかを見てres->nextを返し、0でない場合はresを返します.コードは次のとおりです.

/**
 * 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) {
        //      
        Stack s1= new Stack<>();
        Stack s2 = new Stack<>();
        
        while(l1 != null){
            s1.push(l1.val);
            l1 = l1.next;
        }
        while(l2 != null){
            s2.push(l2.val);
            l2 = l2.next;
        }
        
        int sum = 0;
        ListNode p1 = new ListNode(0);
        while(!(s1.isEmpty() && s2.isEmpty())){
            if(!s1.isEmpty()){
                sum += s1.pop();
                
            }
            if(!s2.isEmpty()){
                sum += s2.pop();

            }
            
            p1.val = sum % 10;
            ListNode p2 = new ListNode(sum / 10);
            p2.next = p1;
            p1 = p2;
            sum /=10;
        }
        return sum == 0 ? p1.next : p1; //                                           
    }
}

 
次の方法は再帰を用いて実現され、再帰も実際にスタックで各状態を保存することを知っているので、後から数字を取ることができ、まず2つのチェーンテーブルの長さを統計し、それから長さに基づいて再帰関数を呼び出し、パラメータの差を伝える必要があり、再帰関数パラメータのl 1チェーンテーブルの長さはl 2より長く、再帰関数の中で、差分値が0でない場合、ノード値がl 1の値である場合、0である場合、l 1とl 2の和を確立し、差分値に基づいて再帰関数を呼び出してノードpostを求め、キャリーを処理し、postの値が9より大きい場合、10に対して残りを取り、resの値を1から増やし、posをresの後に接続してresに戻り、最後に元の関数に戻ります.キャリーの処理は、次のコードを参照してください.
ここでは、いくつかの点を明確にします.
1.addTwoNumbersでもキャリーを考慮する必要がある[5],[5]help関数にpostが存在しないキャリーを考慮できない場合や[9,2][9]の場合も
2.help関数は直接加算されたノードresとそのnextノードpostがpostの値に基づいてキャリーを考慮する場合を処理する

/**
 * 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) {
        int length1= sumLength(l1), length2 = sumLength(l2);
        int diff = length1 - length2;        
        
        ListNode head = new ListNode(1);
        head.next = diff > 0 ? help(l1, l2, diff) : help(l2,l1, -diff);
        if(head.next.val > 9){
            head.next.val %= 10;
            return head;
        }
        return head.next;
    }
    private int sumLength(ListNode node){
        int sum = 0;
        while(node.next != null){
            node = node.next;
            sum++;
        }
        return sum;
    }
    private ListNode help(ListNode l1, ListNode l2, int diff){
        if(l1 == null)
            return null;
        ListNode res = diff == 0 ? new ListNode(l1.val + l2.val) : new ListNode(l1.val);
        ListNode post = diff == 0 ? help(l1.next, l2.next, 0) : help(l1.next, l2, diff - 1);
        if(post != null && post.val > 9){
            post.val %= 10;
            res.val++;
        }
        res.next = post;
        return res;
    }
}