Как вынести 1 из остатка при суммировании двух связанных списков?

Question

У меня объявлено два связанных списка, которые содержат набор чисел, представляющих целое число. Для этого примера я использую x = 666 и y = 666, потому что в этом случае ему нужно иметь дело с остатком и добавлением 1 к следующему целому числу для каждой итерации.

Целые числа автоматически генерируются и помещаются в связанный список в обратном порядке. Эти связанные списки, однако, могут иметь любую длину в зависимости от сгенерированного целого числа. Как мне справиться с переносом и остатками при суммировании двух списков вместе?

Answer 1

Я предполагаю, что мы храним цифры в списках от наименее значимой цифры до самой значимой цифры.Другими словами, число 143 будет представлено в виде списка следующим образом:

  [3] -> [4] -> [1]
   ^             ^
   |             |
 front         back

Хранение старших значащих цифр в заголовке делает добавление менее эффективным, поскольку для определения длины списков необходимы дополнительные обходы.

---

В этом коде нужно разрешить несколько проблем:

1. while (xInter.hasNext()) { // check if there is any numbers проверяет, есть ли у x числа, что работает, только если списки совпадаютдлина или x длиннее.Вместо этого продолжайте итерацию, пока либо xIt, либо yIt имеет число, потому что предстоит еще много работы.

2. Вместо попытки добавить новый элемент результата, как только вы поймете, чтопора переносить с result.add(rem); // add remainder to result list., я рекомендую отложить добавление остатка до тех пор, пока он действительно не понадобится на следующей итерации.Кажется, проще строго придерживаться интуиции арифметического подхода, когда он выполняется вручную.

   Кроме того, llist1.set(pos++, xInter.next() + 1); // add 1 to next int. сложно, потому что вы сделали шаг вперед, не имея возможности вернуться назад.Логика становится запутанной, и на следующем шаге необходимо знать слишком много состояний.На любом шаге удалите только один элемент из каждого итератора и добавьте только один узел к результату.

3. Следуя последнему пункту, я бы также рекомендовал удалить большинство переменных иветвления.pos и carryBool не нужны и усложняют понимание кода.

В своем переписывании я продолжаю добавлять, пока оба итератора не опустеют.Любые пустые итераторы объединяются в 0, и мы можем продолжить нормальное вычисление.Для каждой операции сложения мы делаем две вещи: 1) вычисляем элемент для текущей цифры результата и 2) передаем остаток до следующей цифры, если необходимо.

Вот полный пример:

import java.util.*;
import static java.lang.System.out;

class Main {
    public static LinkedList<Integer> add(
        LinkedList<Integer> a, LinkedList<Integer> b
    ) {
        LinkedList<Integer> result = new LinkedList<>();
        Iterator<Integer> xIt = a.iterator();
        Iterator<Integer> yIt = b.iterator();
        int rem = 0;

        while (xIt.hasNext() || yIt.hasNext()) {
            int x = xIt.hasNext() ? xIt.next() : 0;
            int y = yIt.hasNext() ? yIt.next() : 0;
            result.add((x + y + rem) % 10);
            rem = x + y + rem >= 10 ? 1 : 0;
        }

        if (rem > 0) {
            result.add(rem);
        }

        return result;
    }

    public static void main(String[] args) {
        int[][] tests = {
            {143, 675},
            {77666, 666},
            {985, 824},
            {9999, 1},
            {1, 9999},
            {667, 677},
        };

        for (int[] test : tests) {
            LinkedList<Integer> a = itol(test[0]);
            LinkedList<Integer> b = itol(test[1]);
            LinkedList<Integer> sum = add(a, b);
            int expected = test[0] + test[1];

            out.println("a   : " + a + "\n" + "b   : " + b);
            out.println("sum : " + sum);
            out.println(test[0] + " + " + test[1] + " = " + ltoi(sum));
            out.println("Correct? " + (ltoi(sum) == expected) + "\n");
        }
    }

    private static LinkedList<Integer> itol(int i) {
        LinkedList<Integer> res = new LinkedList<>();

        for (; i > 0; i /= 10) res.offer(i % 10);

        return res;
    }

    private static int ltoi(LinkedList<Integer> ll) {
        String digits = "";

        for (int i : ll) digits = i + digits;

        return Integer.parseInt(digits);
    }    
}

Вывод:

a   : [3, 4, 1]
b   : [5, 7, 6]
sum : [8, 1, 8]
143 + 675 = 818
Correct? true

a   : [6, 6, 6, 7, 7]
b   : [6, 6, 6]
sum : [2, 3, 3, 8, 7]
77666 + 666 = 78332
Correct? true

a   : [5, 8, 9]
b   : [4, 2, 8]
sum : [9, 0, 8, 1]
985 + 824 = 1809
Correct? true

a   : [9, 9, 9, 9]
b   : [1]
sum : [0, 0, 0, 0, 1]
9999 + 1 = 10000
Correct? true

a   : [1]
b   : [9, 9, 9, 9]
sum : [0, 0, 0, 0, 1]
1 + 9999 = 10000
Correct? true

a   : [7, 6, 6]
b   : [7, 7, 6]
sum : [4, 4, 3, 1]
667 + 677 = 1344
Correct? true