Как добавить два целых числа, представленные в виде двух непустых связанных списков?

Question

Вопрос: Вам даны два непустых связанных списка, представляющих два неотрицательных целых числа. Цифры хранятся в обратном порядке, и каждый из их узлов содержит один ди git. Добавьте два числа и верните их в виде связанного списка. Можно предположить, что два числа не содержат начального нуля, кроме самого 0 **

Пример: рабочий тестовый сценарий выглядит следующим образом: - Ввод: (2 -> 4 -> 3) + (5 -> 6 -> 4) - Выход: 7 -> 0 -> 8 - Объяснение: 342 + 465 = 807.

Мое решение не работает для следующего теста:

• Вход:
  • [9]
  • [1,9,9,9,9,9,9,9,9,9]
• Вывод: [0, -4, -6, -3, -8, -4, -7, -4, -1, -2]
• Ожидается: [0,0,0,0,0,0 , 0,0,0,0,1]

Определение для односвязного списка:

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

Это мое решение

import java.lang.Math;

class Solution 
{

public ListNode addTwoNumbers(ListNode l1, ListNode l2) 
{
        int count = 0;
        int number1=0;
        int number2=0;
        int temp=0;

        while(l1 !=null)
        {
            temp = l1.val;
            number1 += temp*Math.pow(10,count);
            count++;
            l1= l1.next;
         }

        count = 0;

        while(l2 !=null)
        {
            temp = l2.val;
            number2 += temp*Math.pow(10,count);
            count++;
            l2= l2.next;
        }

        int sum = number1 + number2;
        ListNode l3 = new ListNode(sum%10);
        ListNode l4 = l3;

        while(sum!=0)
        {
          sum=sum/10;
          if (sum!=0) 
          {
          l3.next = new ListNode(sum%10);
          l3=l3.next; 
          } 

        }
        return l4;  

 }
}

Answer 1

У вас целочисленное переполнение. [1,9,9,9,9,9,9,9,9,9] должно представлять число 9 999 999 991. Вы пытаетесь преобразовать список в int (number1), но наибольшее число, которое может содержать int, составляет 2 147 483 647, поскольку int - это 32-разрядное целое число со 2-мя знаками.

В этой ситуации было бы очень хорошо, если бы Java выдал исключение, чтобы мы знали, почему оно не работает. Нет такой удачи. Вместо этого он просто отбрасывает старшие биты, превышающие 32 бита, давая какое-то бессмысленное отрицательное значение (отрицательное, потому что бит знака (первый бит) равен 1).

Итак, вам нужно выполнить добавление напрямую в виде связанных списков без преобразования в int и обратно. Вы можете очень удобно иметь три связанных списка, каждый из которых содержит до 11 элементов (а также до миллиона элементов, если вам это нужно), так что это не вызовет переполнения.

Если вы не знаете, какое число c переполнение, пожалуйста, посмотрите. Ваша поисковая система - ваш друг.

Answer 2

хотя ваша логика c выглядит нормально, это может привести к переполнению, когда вы сталкиваетесь с большими тестовыми наборами / большими числами, представленными в виде связанных списков.

Я дам вам совет, не конвертируйте узлы связанного списка в число. Есть способ сделать это по-другому, просто с помощью обычной итерации связанных списков.

Попробуйте подумать о том, как вы обычно добавляете числа, как нас учили в школе, записывая их на бумаге.