Вычтите 1 из числа, представленного в виде связанного списка

Учитывая, что заголовок связанного списка представляет собой положительное целое число, задача состоит в том, чтобы напечатать обновленный связанный список после вычитания из него 1.

Примеры:

Input: LL = 1 -> 2 -> 3 -> 4
Output: 1 -> 2 -> 3 -> 3

Input: LL = 1 -> 2
Output: 1 -> 1

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

• Определите функцию, скажем, subtractOneUtil(Node *head) , которая принимает заголовок связанного списка в качестве аргументов, и выполните следующие шаги:
  • Базовый случай: если головной узел связанного списка имеет значение NULL , верните -1 из этого рекурсивного вызова.
  • Рекурсивный вызов : Рекурсивный вызов следующего узла связанного списка и пусть значение, возвращаемое этим рекурсивным вызовом, будет заимствовано .
  • Если значение заимствования равно -1 , а значение головного узла равно 0 , то значение головного узла обновляется до 9 и возвращается -1 из текущего рекурсивного вызова.
  • В противном случае уменьшите значение головного узла на 1 и верните 0 из текущего рекурсивного вызова.
• Вычтите 1 из связанного списка, вызвав вышеуказанную функцию как subtractOneUtil(head) .
• Если связанный список обновлений имеет начальные 0 , переместите указатель заголовка.
• После выполнения вышеуказанных шагов распечатайте обновленный связанный список как результирующий связанный список.

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

Временная сложность: O(N), N — длина данного связанного списка .
Вспомогательное пространство: O(1)