Простой подход к вопросам «Связанный список» и «Добавление двух чисел»
Даны два числа, представленные двумя списками, которые вернут сумму списка. Список сумм представляет собой список сложения двух входных чисел.
Ввод : List1: 9->4->2// represents number 249
List2: 6->5->4 // represents number 456
Output: Resultant list: 5->0->7 // represents number 705 Explanation: 249 + 456 = 705
Решение
Давайте узнаем, как создать узел. Узел будет иметь свои собственные данные и указатель, который будет указывать на следующий узел.
// singly-linked list.
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
Теперь давайте создадим два связанных списка, например -
// creating first list, actual number is
249head1 = new
Node(9); head1.next = new
Node(4); head1.next.next = new
Node(2);
// creating second list, actual number is
456head2 = new
Node(6); head2.next = new
Node(5); head2.next.next = new
Node(4);
Давайте передадим head1 и head2 методу addTwoLists
,
sumofTwoNumberList = addTwoLists(head1, head2);
Окончательное решение будет выглядеть так:
- Мы перевернули связанные списки, и нам нужно перебрать каждый из них и добавить значения из обоих списков друг в друга. В результате нам нужно вернуть новый связанный список с суммой значений.
- Нам нужно нести ценность. Потому что в каждом узле должно быть однозначное значение. Если вы сложите 5 + 5, результат будет 10, так что вы живете 0 в последнем узле и перемещаете 1 на следующий узел. И в следующем узле вы добавите к сумме 1.
let carryOver = 0 let addTwoLists = function(head1, head2) { if(!head1 && !head2 && carryOver === 0) { return null; } let headValue1 = head1 ? head1.data : 0; let headValue2 = head2 ? head2.data : 0; let sum = carryOver + headValue1 + headValue2; carryOver = Math.floor(sum/10); let nextHead1 = head1 ? head1.next : null; let nextHead2 = head2 ? head2.next : null; return { value: sum % 10, next: addTwoLists(nextHead1, nextHead2) }; }; addTwoLists(head1, head2)
Вывод,
Эта задача очень популярна при собеседовании по кодированию.
Продолжайте учиться, продолжайте расти!
Не забывайте подписываться на меня, чтобы увидеть больше таких статей, и подписаться на нашу рассылку новостей.
Давайте подключимся к LinkedIn !. Пожалуйста, прочтите дополнительные вопросы о javascript структуры данных.
Не забудьте подписаться на публикацию The Lean Programmer Publication, чтобы увидеть больше таких статей, и подпишитесь на нашу новостную рассылку tinyletter.com/TheLeanProgrammer