给定存储两个数字数字的 LinkedLists，将数字相加

Question

您好，我正在尝试解决一些问题，但无法确定我的错误。:(

问题描述：

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: l1 = [2,4,3], l2 = [5,6,4]

Output: [7,0,8]

Explanation: 342 + 465 = 807.

我的代码：

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        
        String firstNumber = "";
        String secondNumber = "";
        
        // Converts the lists into strings
        while (l1 != null){
            
            firstNumber += Integer.toString(l1.val);
            l1 = l1.next;
            
        }
        
        while (l2 != null){
            
            secondNumber += Integer.toString(l2.val);
            l2 = l2.next;
            
        }
        
        // Reverses the strings
        firstNumber = new StringBuilder(firstNumber).reverse().toString();
        secondNumber = new StringBuilder(secondNumber).reverse().toString();
        
        long additionLong = Long.parseLong(firstNumber) + Long.parseLong(secondNumber);
    
        ListNode solutionList = new ListNode();
        ListNode prevNode = new ListNode();
        ListNode currentNode = solutionList;
        
        while (additionLong > 0){
            
            currentNode.val = (int) additionLong % 10;
            additionLong /= 10;
            
            ListNode nextNode = new ListNode();
            currentNode.next = nextNode;
            prevNode = currentNode;
            currentNode = currentNode.next;
            
        }
        
        prevNode.next = null;
            
        return solutionList;
            
    }
}

我无法通过以下测试，我似乎无法确定问题所在..

Input

l1 = [9]

l2 = [1,9,9,9,9,9,9,9,9,9]

My Output

[8,0,0,0,0,0,0,0,0,0,1]

Expected

[0,0,0,0,0,0,0,0,0,0,1]

我怀疑麻烦的步骤是当我将两个反转的字符串加在一起时，但代码确实通过了一些其他测试，所以我不明白为什么它不能通过这个..

此外，到目前为止，在我的学位课程中，我们只有 Java 和 C 的 2 门非常基础的入门课程，而且我们只涵盖了基础知识，因此我们并没有真正学会如何写好代码。 . 如果我在我的代码中做了一些愚蠢的事情，请告诉我，这样我就知道要避免它了。 :)

Answer 1

你的方法好像有点复杂。你在做一道算术题；它可能不是涉及字符串的正确方法。

想一想你（也许）是如何在小学学习加法的：你添加列，从最低有效数字开始，将任何超过 10 的数字带到下一列。

这里的问题被最低有效数字排在第一位这一事实简化了。因此，您只需要为当前列创建一个新节点，计算它的值，并将任何内容转移到下一列。

由于列表的长度可能不同，这有点复杂，但这并不难处理：如果您在一个列表中“运行超出”数字，您可以假装它包含一个零。

这段代码只会打印出总和的数字；如果需要，您应该尝试找出如何构建包含结果的链表：

int carry = 0;
// We want to iterate while there is something more to add - even if
// we have exceeded the length of one or both lists, we may still have carry.
while (l1 != null || l2 != null || carry != 0) {
  // Get the value from each of the lists. If we've gone past the end of
  // a list, just use zero as the value.
  int i1 = l1 != null ? l1.value : 0;
  int i2 = l2 != null ? l2.value : 0;

  int value = i1 + i2 + carry;

  // The next carry is the tens of value.
  carry = value / 10;

  // The value in the current column are the units of value.
  value = value % 10;

  // Print out the value in the current column.
  System.out.println(value);

  // Advance the two linked lists (assuming we've not reached the end already).
  if (l1 != null) l1 = l1.next;
  if (l2 != null) l2 = l2.next;
}

Answer 2

将列表转换为字符串后：

    String  firstNumber = "243"; //or firstNumber = "9";
    String  secondNumber = "564";//secondNumber = "1999999999";
    // Reverses the strings
    firstNumber = new StringBuilder(firstNumber).reverse().toString();
    secondNumber = new StringBuilder(secondNumber).reverse().toString();
    //add
    Long sum = Long.valueOf(firstNumber)+ Long.valueOf(secondNumber);
    //reverse sum
    String output = new StringBuilder(String.valueOf(sum)).reverse().toString();
    System.out.println(output);

如果您需要将输出拆分为一个数组，只需将其更改为：

    //reverse sum and split it
    String[] output = new 
    StringBuilder(String.valueOf(sum)).reverse().toString().split("");
    System.out.println(Arrays.toString(output));

Answer 3

如果你有一把锤子，每个问题看起来都像钉子。

使用字符串也是一样。

而是显示更抽象的方法。

如果你有 67 [7, 6] 和 398 [8, 9, 3] 你会怎么加？

7+8 给 5 进位 1
6+9+进位 6 进位 1
N/A+3+进位 4 进位 0
N/A+N/A+进给N/A

所以：

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode sum = null;
    ListNode last = null;

    int carry = 0;
    while (l1 != null || l2 != null) {
        int sum = carry;
        if (l1 != null) {
            sum += l1.value;
            l1 = l1.next;
        }
        if (l2 != null) {
            sum += l2.value;
            l2 = l2.next;
        }
        carry = 0;
        if (sum >= 10) {
            carry = 1;
            sum -= 10;
        }
        ListNode sumNode = ...
        ...
    }
    if (carry != 0) { // An extra digit.
        ...
    }
    return sum;
}

Answer 4

if I did something silly in my code please let me know so I know to avoid it.

将结果转换为 long 时出现问题：

 currentNode.val = (int) additionLong % 10;

这会将 additionLong 转换为 int，这将导致损失，然后才将 % 10 应用于此。您需要：

 currentNode.val = (int) (additionLong % 10);

这将解决此特定测试用例的问题。

正如其他人所说，您应该考虑在不在链表、字符串和长整数之间进行转换的情况下执行此操作。你可能会遇到long容量不够用的测试用例，然后就真的卡住了。

而是坚持只使用链表，逐位处理。这就是练习的目的。

给定存储两个数字数字的 LinkedLists，将数字相加

Given LinkedLists that store the digits of two numbers, add the numbers together

java

math

linked-list