Добавьте два числа, представленные связанным списком
Имея два числа, представленные двумя списками, напишите функцию, которая возвращает сумму в виде связанного списка.
Пример :
Input:
List1: 5->6->3 // represents number 563
List2: 8->4->2 // represents number 842
Output:
Resultant list: 1->4->0->5 // represents number 1405
Explanation: 563 + 842 = 1405Input:
List1: 7->5->9->4->6 // represents number 75946
List2: 8->4 // represents number 84
Output:
Resultant list: 7->6->0->3->0// represents number 76030
Explanation: 75946+84=76030
Пройдите оба списка до конца и добавьте предшествующие нули в список с меньшими цифрами. Затем вызовите рекурсивную функцию для начальных узлов обоих списков, которая вызывает себя для следующих узлов обоих списков, пока не дойдет до конца. Эта функция создает узел для суммы текущих цифр и возвращает перенос.
Выполните следующие шаги, чтобы решить проблему:
- Перейдите два связанных списка, чтобы добавить предшествующие нули, если в списке меньше цифр, чем в другом.
- Начните с головного узла обоих списков и вызовите рекурсивную функцию для следующих узлов.
- Продолжайте до конца списков.
- Создает узел для текущей суммы цифр и возвращает перенос.
Ниже приведена реализация этого подхода.
Временная сложность: O(m + n), где m и n — количество узлов в первом и втором списках соответственно. Списки необходимо пройти только один раз.
Вспомогательное пространство: O (m + n). Для хранения выходного числа необходим временный связанный список.
Добавьте два числа, представленные связанными списками, используя Stack :
Следуйте инструкциям, чтобы решить проблему:
- Создайте 3 стопки, а именно s1, s2, s3.
- Заполните s1 узлами списка1 и заполните s2 узлами списка2.
- Заполните s3, создав новые узлы и установив данные новых узлов в сумму s1.top(), s2.top() и сохраняя до тех пор, пока list1 и list2 не станут пустыми.
- Если сумма больше 9, установить перенос 1
- В противном случае установите перенос 0
- Создайте узел (скажем, предыдущий), который будет содержать заголовок списка сумм.
- Свяжите все элементы s3 сверху вниз.
- Верните предыдущий узел в качестве результата.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(n), здесь n — длина большего списка
Вспомогательное пространство: O(n). Дополнительное пространство используется для хранения элементов в стеке.
Добавьте два числа, представленные связанными списками, с помощью Traversing On Larger List:
Выполните следующие шаги, чтобы решить проблему:
- Сначала мы вычисляем размеры обоих связанных списков, size1 и size2 соответственно.
- Затем мы проходим по большему связанному списку, если он есть, и уменьшаем его до тех пор, пока размер обоих не станет одинаковым.
- Теперь проходим оба связанных списка до конца.
- Теперь возврат происходит при выполнении сложения.
- Наконец, головной узел возвращается в связанный список, содержащий ответ.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(M + N), где M и N — размер списка 1 и списка 2 соответственно.
Вспомогательное пространство: O(1)
Связанная статья: Добавление двух чисел, представленных связанными списками | Набор 2
Добавьте два числа, представленные связанными списками, без добавления нулей:
In this approach we simulate how in reality we add two numbers. In the code we have taken 9->8->7 and 1->2->3 as two numbers to add. What we do is reverse these two lists to get 7->8->9 and 3->2->1 and start from the head of the lists to add numbers of individual nodes like we would in practice if we add two numbers.
For example, first we add 7 and 3 to get 10, which means carry = 1 and value of new node will be 0. Now we continue this till the end of the list.
Выполните следующие шаги, чтобы решить проблему:
- Переверните два списка чисел.
- Имитация добавления узлов один за другим. Добавьте каждый узел перед уже рассчитанными узлами суммы (вы лучше поймете этот шаг в коде).
- В итоге мы получим окончательный ответ и сможем вернуть головной узел.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(max(M, N)), где M и N — количество узлов в первом и втором списках соответственно. Списки необходимо пройти только один раз.
Космическая сложность: O(1)