Программа Javascript для написания функции для получения N-го узла в связанном списке

Опубликовано: 8 Октября, 2022

Напишите функцию GetNth(), которая принимает связанный список и целочисленный индекс и возвращает значение данных, хранящееся в узле в этой позиции индекса.

Пример:

Input:  1->10->30->14,  index = 2
Output: 30  
The node at index 2 is 30

Алгоритм:

1. Initialize count = 0
2. Loop through the link list
     a. If count is equal to the passed index then return 
        current node
     b. Increment count
     c. change current to point to next of the current.

Реализация:

Выход:

Element at index 3 is 4

Временная сложность: O(n)

Сложность пространства: O(1), поскольку для создания узлов и переменных используется постоянное пространство.

Метод 2- с рекурсией:

Алгоритм:

getnth(node,n)
1. Initialize count = 0
2. if count==n
     return node->data
3. else
    return getnth(node->next, n-1)

Реализация:

Выход:

Element at index 3 is 4

Временная сложность: O(n)

Сложность пространства : O(1), так как используется постоянное пространство для узлов и переменных.

Пожалуйста, обратитесь к полной статье о написании функции для получения N-го узла в связанном списке для получения более подробной информации!