Обяснено решение на проблем с HackerRank
За днешния алгоритъм ще вмъкнем възел в началото на единично свързан списък. Ето предизвикателството, което избрах от HackerRank:
При даден указател към главата на свързан списък, вмъкнете нов възел преди главата. Следващата стойност в новия възел трябва да сочи към head и стойността data трябва да бъде заменена с дадена стойност. Върнете препратка към новата глава на списъка. Даденият начален указател може да е нула, което означава, че първоначалният списък е празен.
Проблемът е ясен, нека преминем към решението:
- Инициализирайте клас възел.
- Създайте нов възел с дадената стойност.
- Ако списъкът е празен, задайте новия възел като глава и го върнете.
- Ако списъкът не е празен, задайте следващия от новия възел като глава и след това променете показалеца на главата, за да сочи към новия възел.
- Върнете новата глава на актуализирания свързан списък.
Горните стъпки са илюстрирани по следния начин:
Ето моят код в JavaScript:
Като се има предвид препратка към главата на списък, от нас се иска да добавим нов възел в началото на списъка. Методът приема два аргумента; главата на свързания списък и стойност за вмъкване. Първо създаваме възел от входната стойност и новодобавеният възел става новата глава на свързания списък, след като зададе връзката си към предишната глава на дадения свързан списък.
Както виждате в този пример, е много лесно да добавите възел в началото на свързания списък и това може да се направи с постоянна или O(1) времева сложност. Надявам се да намерите тази статия за полезна, благодаря ви, че я прочетохте!