Добавьте два числа, представленные связным списком, без дополнительного пробела

Опубликовано: 27 Февраля, 2023

Имея два числа, представленные двумя связанными списками, напишите функцию, которая возвращает список сумм. Список сумм представляет собой связанный список, представляющий собой сложение двух входных чисел. Ожидаемая космическая сложность O(1).

Примеры:

Input: 
L1 = 5 -> 6 -> 3 -> NULL 
L2 = 8 -> 4 -> 2 -> NULL 
Output: 1 -> 4 -> 0 -> 5 -> NULL

Input: 
L1 = 1 -> 0 -> 0 -> NULL 
L2 = 9 -> 1 -> NULL 
Output: 1 -> 9 -> 1 -> NULL 

Подход: здесь мы обсудили решение, в котором мы использовали рекурсию для достижения наименьшего значимого числа в списках, но из-за участия стека пространственная сложность решения становится O (N)
Здесь цель состоит в том, чтобы сделать сумму на месте и вернуть измененный список сумм.

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

Ниже приведены шаги:

  1. Обратный список L1.
  2. Обратный список L2.
  3. Добавляйте узлы обоих списков итеративно.
  4. Переверните получившийся список и верните его заголовок.

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

Временная сложность: O(max(m, n)), где m и n — количество узлов в списках l1 и l2 соответственно.
Космическая сложность: O(1)

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