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

Ограничения по хранению номера

Мы можем хранить наше число x в массиве, при этом каждый индекс массива хранит цифры числа. Поскольку мы используем здесь массив, величина числа x, которое мы можем сохранить, зависит от размера массива. Теперь массив, объявленный статически, хранится в разделе стека памяти. Мы не можем зафиксировать размер массива каким-либо произвольным числом. Существует верхний предел максимального размера массива. Это ограничение размера массива зависит от аппаратного обеспечения системы. Для целочисленного массива ограничение на размер обычно составляет около 10⁶. Чтобы узнать больше об ограничении размера, загляните здесь.

Но что делать, если длина числа больше максимально допустимого размера массива. Как вы добавите один к x, если вы даже не можете его сохранить? Чтобы обойти это препятствие, мы будем использовать динамический раздел памяти с помощью связанных списков. Так же, как каждый индекс массива хранил цифру числа, каждый узел списка будет хранить то же самое (конечно, в дополнение к следующему указателю). Используя этот подход, мы можем хранить число без ограничений. Теперь давайте обсудим, как добавить единицу к x. Прежде чем читать следующий раздел, подумайте о различных возможных подходах.

Предположим, у нас есть заголовок связанного списка, в котором хранится число x. Если в заголовке хранится наиболее значимая цифра числа, тогда нам потребуется выполнить итерацию до конца списка и увеличить наименьшую значащую цифру (lsd) на единицу. Мы закончили бы свою работу, только если бы lsd не было цифрой 9, поэтому для завершения операции потребуется только обход. Но что, если последняя цифра - 9, скажем, число вроде 1239. В таком случае вам нужно будет вернуться к предыдущему узлу и добавить к нему перенос. Опять же, что, если в предыдущем узле тоже есть 9? Как вы можете видеть в таком случае, вам нужно будет продолжать итерацию назад, пока вы не получите цифру, отличную от 9. Другими словами, найдите заголовок непрерывного блока из девяток так, чтобы последняя цифра смежного блока из девяток и число, хранящееся в связанном списке, - 9. Теперь все, что вам нужно сделать, это изменить значение цифр в узлах связанного списка.

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

  • В первом подходе сначала нам нужно перевернуть связанный список. Таким образом, в начале списка будет наименее значимая цифра. Вместо того, чтобы возвращаться к предыдущему узлу, чтобы проверить, есть ли у него цифра 9, теперь нам просто нужно двигаться вперед и делать то же самое. После того, как мы закончили с добавлением, мы можем снова перевернуть список, и в голове снова будет самая значимая цифра числа. Этот метод требует трех обходов списка для завершения задания: один для переворота списка, второй для выполнения сложения и третий для повторного обращения списка. Перейдите ко второму способу, чтобы сделать то же самое всего за один обход списка!
  • Этот метод немного сложен. Для обхода списка мы поддерживаем две переменные-указатели - ptr1 и ptr2. Инициализируем оба указателя заголовком списка. Мы просматриваем список последовательно и перемещаем оба указателя вместе, пока не встретим 9. На этом этапе мы перемещаем один из указателей, скажем, ptr2, до тех пор, пока не найдем 9. Если ptr2 достигает конца списка, мы используем другой указатель, ptr1, для обновления значений узлов списка. Но если мы не дойдем до конца списка и цепочка из 9 разрывов, просто обновите значение ptr1 таким же, как ptr2, и продолжите тот же процесс, что обсуждается в методе.

Обратите внимание на два угловых случая - когда сама голова равна нулю и когда все цифры в числе равны 9. Они рассмотрены в приведенном выше коде. Этот метод выполняет сложение за O (n), где n - это размер списка с только одним обходом списка.