PUERTA | GATE-IT-2004 | Pregunta 13

Sea P una lista enlazada simple. Sea Q el puntero a un Node intermedio x en la lista. ¿Cuál es la complejidad temporal en el peor de los casos del algoritmo más conocido para eliminar el Node x de la lista?
(A) O(n)
(B) O(log2 n)
(C) O(logn)
(D) O(1)

Respuesta: (D)
Explicación: Una solución simple es recorrer la lista enlazada hasta encontrar el Node desea eliminar. Pero esta solución requiere apuntar al Node principal que contradice la declaración del problema.

La solución rápida es copiar los datos del siguiente Node al Node que se eliminará y eliminar el siguiente Node. Algo así como seguir.

    // 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);

La complejidad temporal de este enfoque es O(1)

Consulte esto para la implementación.

Tenga en cuenta que este enfoque no funciona cuando el Node a eliminar es el último Node. Como la pregunta dice Node intermedio, podemos usar este enfoque.

Cuestionario de esta pregunta