文字列を使用して2つの数字（リンクされたリストの桁）を追加する

Question

2つの非負の数字を追加しようとしています。その数字は2つの別々のリンクリストに逆順で格納されます。また、答えは数字を逆にして末尾のゼロをつけたリンクリストにする必要があります。

私は数字を追加してキャリーを毎回維持することでこの問題を解決する方法があることを理解していますが、数字に加算演算を使用して解決しようとしています。

は、ここに私のコードです：

/** 
    * Definition for singly-linked list. 
    * class ListNode { 
    *  public int val; 
    *  public ListNode next; 
    *  ListNode(int x) { val = x; next = null; } 
    * } 
    */ 
    public class Solution { 
     public ListNode addTwoNumbers(ListNode a, ListNode b) { 
      if(a==null || b==null){ 
       return null; 


} 
     String num1 = ""; 
     String num2 = ""; 
     ListNode temp1 = a; 
     ListNode temp2 = b; 
     while(temp1!=null){ 
      num1 = num1+Integer.toString(temp1.val); 
      temp1 = temp1.next; 
     } 
     new StringBuilder(num1).reverse().toString(); 
     double value1 = Double.parseDouble(num1); 
     while(temp2!=null){ 
      num2 = num2+Integer.toString(temp2.val); 
      temp2 = temp2.next; 
     } 
     new StringBuilder(num2).reverse().toString(); 
     double value2 = Double.parseDouble(num2); 
     double result = value1+value2; 
     String res = String.format("%.0f",result); 
     ListNode first_node = new ListNode(Character.getNumericValue(res.charAt(0))); 
     ListNode ans = first_node; 
     for(int j=1;j<res.length();j++){ 
      ListNode node = new ListNode(Character.getNumericValue(res.charAt(j))); 
      add(node,ans); 
     } 
     return ans; 
    } 
    public void add(ListNode node, ListNode ans){ 
     ListNode temp; 
     temp = ans; 
     ans = node; 
     ans.next = temp; 
    } 
} 

私のコードは、間違った答えを与えてきました。誰でもエラーを指摘できますか？

Answer 1

あなたのアプローチは正しくなく、間接的ではありません。 浮動小数点演算を使用して大きな数字の算術演算を実行しようとしています。 結果として、計算エラー。

我々は持っている：

List<Integer> firstNumber; 
List<Integer> secondNumber; 

はfirstNumber > secondNumberを想定できます。

このalogrithmを試してみてください：

List<Integer> result = new ArrayList<>(); 
int i = 0; 
int appendix = 0; 
for (; i < secondNumber.size(); i++) { 
    int sum = firstNumber.get(i) + secondNumber.get(i) + appendix; 
    result.append(sum % 10); 
    appendix = sum/10; 
} 

for (; i < firstNumber.size(); i++) { 
    int sum = firstNumber.get(i) + appendix; 
    result.append(sum % 10); 
    appendix = sum/10; 
} 

if (appendix != 0) 
    result.append(appendix); 

return result; 

Answer 2

あなたのadd関数が不正になります。あなたは期待どおりの逆順で番号を取得します。

また、解決策には質問のポイントがありません。桁数の多い数字があると、あなたのアプローチは失敗します（二重にも限界があります^ 2^1024と思います）。リンクされたリスト表現は、より大きな数を可能にする。

解決策リストを作成する際に、両方のリストを同時にキャリーディジットで繰り返し処理するだけです。これが課題またはコーディング競争の問題である場合、ソリューションは間違っていると判断されます。

Answer 3

addの方法が間違っていて、リストが正しく作成されていません。ここにあなたの方法の最後の部分がadd方法なしで、どのように見えるべきかである：あなたのアプローチで

for(int j=1;j<res.length();j++){ 
    ans.next = new ListNode(Character.getNumericValue(res.charAt(j)));; 
    ans = ans.next; 
} 
return first_node; 

Answer 4

を、変数ANSが更新されていません。あなたはこれを試すことができます。

ans = add(node,ans); 

とあなたのaddメソッドでは、ListNode ANS

Answer 5

あなたのアプローチは簡単ではないですし、結果を期待与えないだろう返すようにする方法を変更します。

ここでは、加算が整数で単純な整数であるため、多くの説明を必要としない単純なアプローチです。

2つの整数の合計が9より大きい場合、次の整数の合計で続けることに注意してください。

class Node { 
    private Object data; 
    private Node next; 
    public Object getData() { return data; } 
    public void setData(Object data) { this.data = data; } 
    public Node getNext() { return next; } 
    public void setNext(Node next) { this.next = next; } 
    public Node(final Object data, final Node next) { 
     this.data = data; 
     this.next = next; 
    } 
    @Override 
    public String toString() { return "Node:[Data=" + data + "]"; } 
} 


class SinglyLinkedList { 
    Node start; 
    public SinglyLinkedList() { start = null; } 

    public void addFront(final Object data) { 
     // create a reference to the start node with new data 
     Node node = new Node(data, start); 

     // assign our start to a new node 
     start = node; 
    } 

    public void addRear(final Object data) { 
     Node node = new Node(data, null); 
     Node current = start; 

     if (current != null) { 
      while (current.getNext() != null) { 
       current = current.getNext(); 
      } 
      current.setNext(node); 
     } else { 
      addFront(data); 
     } 
    } 

    public void deleteNode(final Object data) { 
     Node previous = start; 

     if (previous == null) { 
      return; 
     } 

     Node current = previous.getNext(); 

     if (previous != null && previous.getData().equals(data)) { 
      start = previous.getNext(); 
      previous = current; 
      current = previous.getNext(); 
      return; 
     } 

     while (current != null) { 
      if (current.getData().equals(data)) { 
       previous.setNext(current.getNext()); 
       current = previous.getNext(); 
      } else { 
       previous = previous.getNext(); 
       current = previous.getNext(); 
      } 
     } 
    } 

    public Object getFront() { 
     if (start != null) { 
      return start.getData(); 
     } else { 
      return null; 
     } 
    } 

    public void print() { 
     Node current = start; 

     if (current == null) { 
      System.out.println("SingleLinkedList is Empty"); 
     } 

     while (current != null) { 
      System.out.print(current); 
      current = current.getNext(); 
      if (current != null) { 
       System.out.print(", "); 
      } 
     } 
    } 

    public int size() { 
     int size = 0; 

     Node current = start; 

     while (current != null) { 
      current = current.getNext(); 
      size++; 
     } 
     return size; 
    } 

    public Node getStart() { 
     return this.start; 
    } 

    public Node getRear() { 
     Node current = start; 
     Node previous = current; 
     while (current != null) { 
      previous = current; 
      current = current.getNext(); 
     } 
     return previous; 
    } 
} 

public class AddNumbersInSinglyLinkedList { 
    public static void main(String[] args) { 
     SinglyLinkedList listOne = new SinglyLinkedList(); 
     SinglyLinkedList listTwo = new SinglyLinkedList(); 
     listOne.addFront(5); 
     listOne.addFront(1); 
     listOne.addFront(3); 
     listOne.print(); 
     System.out.println(); 
     listTwo.addFront(2); 
     listTwo.addFront(9); 
     listTwo.addFront(5); 
     listTwo.print(); 
     SinglyLinkedList listThree = add(listOne, listTwo); 
     System.out.println(); 
     listThree.print(); 
    } 

    private static SinglyLinkedList add(SinglyLinkedList listOne, SinglyLinkedList listTwo) { 
     SinglyLinkedList result = new SinglyLinkedList(); 
     Node startOne = listOne.getStart(); 
     Node startTwo = listTwo.getStart(); 
     int carry = 0; 
     while (startOne != null || startTwo != null) { 
      int one = 0; 
      int two = 0; 
      if (startOne != null) { 
       one = (Integer) startOne.getData(); 
       startOne = startOne.getNext(); 
      } 
      if (startTwo != null) { 
       two = (Integer) startTwo.getData(); 
       startTwo = startTwo.getNext(); 
      } 
      int sum = carry + one + two; 
      carry = 0; 
      if (sum > 9) { 
       carry = sum/10; 
       result.addRear(sum % 10); 
      } else { 
       result.addRear(sum); 
      } 
     } 
     return result; 
    } 
} 

実行サンプル

Node:[Data=3], Node:[Data=1], Node:[Data=5] 
Node:[Data=5], Node:[Data=9], Node:[Data=2] 
Node:[Data=8], Node:[Data=0], Node:[Data=8]