Простой подход к вопросам «Связанный список» и «Добавление двух чисел»

Даны два числа, представленные двумя списками, которые вернут сумму списка. Список сумм представляет собой список сложения двух входных чисел.

Ввод :
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 249
head1 = new Node(9);
head1.next = new Node(4);
head1.next.next = new Node(2);
// creating second list, actual number is 456
head2 = 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