使用字符串添加给定的两个数字（链接列表中的数字）

Question

我想添加两个非负数，其中的数字以相反的顺序存储在两个单独的链接列表中。答案也应该是一个链接列表，其中的数字反转并且不包含尾随零。

我知道有一种方法可以通过每次添加数字和保持进位来解决这个问题，但我试图通过在数字上使用加法操作来解决此问题。

这里是我的代码：

/** 
    * 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

你的附加功能看起来不正确。您将按照与预期相反的顺序得到您的号码。

此外，您的解决方案缺少问题的重点。如果你有一个数字很多的数字（甚至double有它的极限〜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

你的方式方法并不简单，不会给你预期的结果。

这是一个简单的方法，不需要太多的解释，因为加法是整数的简单整数。

请注意，当两个整数之和大于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]