Рубрики

ВОРОТА | GATE-IT-2004 | Вопрос 13

Пусть P — односвязный список. Пусть Q будет указателем на промежуточный узел x в списке. Какова временная сложность наихудшего случая наиболее известного алгоритма удаления узла x из списка?
(A) O (n)
(B) O (log2 n)
(C) O (logn)
(D) O (1)

Ответ: (D)
Объяснение: простое решение — пройти по связанному списку, пока не найдете узел, который хотите удалить. Но это решение требует указателя на головной узел, который противоречит постановке задачи.

Быстрое решение состоит в том, чтобы скопировать данные из следующего узла в удаляемый узел и удалить следующий узел. Что-то вроде следующего.

    // Find next node using next pointer
    struct node *temp  = node_ptr->next;

    // Copy data of next node to this node
    node_ptr->data  = temp->data;

    // Unlink next node
    node_ptr->next  = temp->next;

    // Delete next node
    free(temp);

Временная сложность такого подхода составляет O (1)

Рекомендуемые посты:

ВОРОТА | GATE-IT-2004 | Вопрос 13

0.00 (0%) 0 votes