Программа Java для вычитания двух чисел, представленных в виде связанных списков

Опубликовано: 18 Сентября, 2022

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

Input: l1 = 1 -> 0 -> 0 -> NULL,  l2 = 1 -> NULL
Output: 0->9->9->NULL
Explanation: Number represented as 
lists are 100 and 1, so 100 - 1 is 099

Input: l1 = 7-> 8 -> 6 -> NULL,  l2 = 7 -> 8 -> 9 NULL
Output: 3->NULL
Explanation: Number represented as 
lists are 786 and  789, so 789 - 786 is 3, 
as the smaller value is subtracted from 
the larger one.

Подход: Ниже приведены шаги.

  1. Вычислить размеры заданных двух связанных списков.
  2. Если размеры не совпадают, добавьте нули в меньший связанный список.
  3. Если размер совпадает, выполните следующие действия:
    1. Найдите связанный список с меньшим значением.
    2. Один за другим вычтите узлы связанного списка меньшего размера из большего размера. Следите за заимствованием при вычитании.

Ниже приведена реализация вышеуказанного подхода.

Выход:

0 9 9

Анализ сложности:

  • Временная сложность: O(n).
    Поскольку не требуется вложенный обход связанного списка.
  • Вспомогательное пространство: O(n).
    Если принять во внимание рекурсивное пространство стека, требуется O (n) пространства.

Пожалуйста, обратитесь к полной статье о вычитании двух чисел, представленных в виде связанных списков, для получения более подробной информации!

РЕКОМЕНДУЕМЫЕ СТАТЬИ