Hinzufügen Anzahl Vertreten durch verlinkte Liste

Question

Ich bin auf dieses Problem fest:

Sie haben zwei Zahlen, die durch eine verknüpfte Liste dargestellt, wobei jeder Knoten eine einzelne Ziffer enthält. Die Ziffern werden in umgekehrter Reihenfolge gespeichert, so dass die Ziffer 1 am Anfang der Liste steht. Schreiben Sie eine Funktion, die die beiden Zahlen addiert und die Summe als verkettete Liste zurückgibt. BEISPIEL Input: (3 -> 1 -> 5), (5 -> 9 -> 2) Ausgang: 8 -> 0 -> 8

Das Problem ist, dass mein Ergebnis ist 8 8 während das Ergebnis sollte 8 0 8 sein. Ich habe die Summe ausgedruckt und es ist 8 10 8 so sollte es funktionieren. Irgendwelche Ideen?

Hier ist mein Code:

public Node addNumbers(Node number1, Node number2) { 

     if(number1 == null && number2 == null) 
      return null; 

     Node sumOf = null; 
     int sum = 0; 
     int carry = 0; 

     while(number1 != null && number2 != null) { 
      sum = number1.data + number2.data + carry; 
      System.out.println(sum); 
      // update carry for next operation 
      if(sum > 9) 
       carry = 1; 
      else 
       carry = 0; 

      if(sum > 9) { 
       if(sumOf == null) { 
        sumOf = new Node(sum % 10); 
       } else { 
        sumOf.next = new Node(sum % 10); 
       } 

      } else { 
       if(sumOf == null) { 
        sumOf = new Node(sum); 
       } else { 
        sumOf.next = new Node(sum); 
       } 

      } 

      number1 = number1.next; 
      number2 = number2.next; 
     } 

     return sumOf; 
    } 

    public void toString(Node node) { 
     System.out.println(); 
     while (node != null) { 
      System.out.print(node.data + " "); 
      node = node.next; 
     } 
    } 

    public static void main(String[] args) { 

     AddTwoNumbers add = new AddTwoNumbers(); 

     number1 = new Node(3); 
     number1.next = new Node(1); 
     number1.next.next = new Node(5); 

     number2 = new Node(5); 
     number2.next = new Node(9); 
     number2.next.next = new Node(2); 

     System.out.println("numbers: "); 
     add.toString(number1); 
     add.toString(number2); 

     System.out.println(); 
     System.out.println("after adding: "); 
     add.toString(add.addNumbers(number1, number2)); 
    } 
} 

Answer 1

Sie immer nur sumOf gesetzt (wenn es null) und sumOf.next (wenn sumOf nicht null ist). Ihre resultierende Liste enthält daher nie mehr als zwei Elemente. Sie müssen das aktuelle Ende Ihrer Liste verfolgen und dort anhängen, anstatt immer an sumOf anzufügen.

Darüber hinaus müssen Sie die Fälle behandeln, in denen eine Eingangsnummer mehr Ziffern als die andere enthält und bei denen Sie nach dem Ausgeben aller Eingangsziffern einen Übertrag ungleich Null haben. Sie behandeln derzeit auch nicht.

Answer 2

/* Adds contents of two linked lists and return the head node of resultant list */ 
    struct Node* addTwoLists (struct Node* first, struct Node* second) 
    { 
     struct Node* res = NULL; // res is head node of the resultant list 
     struct Node *temp, *prev = NULL; 
     int carry = 0, sum; 

     while (first != NULL || second != NULL) //while both lists exist 
     { 
      // Calculate value of next digit in resultant list. 
      // The next digit is sum of following things 
      // (i) Carry 
      // (ii) Next digit of first list (if there is a next digit) 
      // (ii) Next digit of second list (if there is a next digit) 
      sum = carry + (first? first->data: 0) + (second? second->data: 0); 

      // update carry for next calulation 
      carry = (sum >= 10)? 1 : 0; 

      // update sum if it is greater than 10 
      sum = sum % 10; 

      // Create a new node with sum as data 
      temp = newNode(sum); 

      // if this is the first node then set it as head of the resultant list 
      if(res == NULL) 
       res = temp; 
      else // If this is not the first node then connect it to the rest. 
       prev->next = temp; 

      // Set prev for next insertion 
      prev = temp; 

      // Move first and second pointers to next nodes 
      if (first) first = first->next; 
      if (second) second = second->next; 
     } 

     if (carry > 0) 
      temp->next = newNode(carry); 

     // return head of the resultant list 
     return res; 
    } 

Sie können den Link für eine klarere Erklärung sehen. Die Lösung ist sowohl in Java als auch in C++ http://www.geeksforgeeks.org/add-two-numbers-represented-by-linked-lists/

Answer 3

Hier ist die Lösung, beachten Sie, dass ich weitertragen, wenn die Summe von zwei ganzen Zahlen größer als 9 ist, sonst fahre ich mit der Summe der nächsten ganzen Zahlen von beiden Liste.

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; 
    } 
} 

Sample Run

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]