Eliminación de Elementos en Listas Enlazadas (LeetCode 203)

La eliminación de nodos en una lista enlazada es una operación fundamental que presenta particularidades, especialmente al tratar con el primer nodo. Exploraremos dos estrategias principales: la eliminación directa y el uso de un nodo ficticio (dummy head) para simplificar la lógica.

Estrategia 1: Eliminación Directa

Esta aproximación requiere manejar dos escenarios distintos para asegurar la correcta manipulación de la lista:

1. Si el valor del nodo principal (cabeza de la lista) coincide con el objetivo, se debe reasignar la cabeza de la lista al siguiente nodo. Este paso debe repetirse para eliminar una secuencia de nodos coincidentes al inicio (por ejemplo, en la lista [1,1,1,2] con objetivo 1).
2. Si un nodo intermedio cuyo valor coincide con el objetivo necesita ser eliminado, se debe ajustar el puntero next del nodo precedente para que salte al nodo a eliminar y apunte directamente al siguiente.

El proceso genarel implica:

• Primero, una fase para descartar todos los nodos iniciales que tengan el valor especificado, actualizando la cabeza de la lista.
• Luego, un recorrido por el resto de la lista. Se utiliza un puntero currentNode que avanza, y cuando se detecta que currentNode->next tiene el valor objetivo, se maniplua currentNode->next para omitir el nodo a eliminar.
• Finalmente, se retorna la referencia a la nueva cabeza de la lista.

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // Eliminar todos los nodos iniciales que coincidan con 'val'
        while (head != nullptr && head->val == val) {
            ListNode* nodeToDelete = head;
            head = head->next;
            delete nodeToDelete; // Liberar la memoria del nodo eliminado
        }

        // Recorrer el resto de la lista para eliminar nodos intermedios
        ListNode* currentNode = head;
        while (currentNode != nullptr && currentNode->next != nullptr) {
            if (currentNode->next->val == val) {
                ListNode* nodeToDelete = currentNode->next;
                currentNode->next = nodeToDelete->next;
                delete nodeToDelete; // Liberar la memoria del nodo
            } else {
                currentNode = currentNode->next; // Mover al siguiente nodo solo si no se eliminó
            }
        }
        return head; // Retornar la posible nueva cabeza de la lista
    }
};

Estrategia 2: Uso de un Nodo Ficticio (Dummy Head)

La principal ventaja de emplear un nodo ficticio (también conocido como nodo centinela o dummy head) es que unifica el manejo de todos los casos de eliminación. Al introducir un nodo auxiliar al principio, la cabeza real de la lista nunca es el primer nodo que se procesa, eliminando la necesidad de una lógica especial para la eliminación del primer elemento.

Los pasos para esta estrategia son:

1. Crear un dummyHead, un nodo temporal cuyo puntero next se inicializa para que apunte a la cabeza original de la lista.
2. Utilizar un puntero current que se inicializa en dummyHead.
3. Iterar con current a lo largo de la lista. Si se encuentra que el nodo al que apunta current->next tiene el valor objetivo, se "salta" ese nodo. Esto se logra haciendo que current->next apunte directamente a current->next->next.
4. Al concluir el bucle, la cabeza de la lista modificada será dummyHead->next.

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // Crear un nodo ficticio que precede a la cabeza real de la lista
        ListNode* dummyHead = new ListNode(0); // El valor del nodo ficticio no importa
        dummyHead->next = head;

        ListNode* current = dummyHead; // El puntero de recorrido empieza en el nodo ficticio
        while (current->next != nullptr) {
            if (current->next->val == val) {
                ListNode* nodeToDelete = current->next;
                current->next = nodeToDelete->next; // Saltar el nodo
                delete nodeToDelete; // Liberar la memoria del nodo
            } else {
                current = current->next; // Avanzar si no se eliminó el siguiente nodo
            }
        }
        
        // La nueva cabeza de la lista es el siguiente del nodo ficticio
        head = dummyHead->next;
        delete dummyHead; // Liberar la memoria del nodo ficticio
        return head;
    }
};

Diseño de una Lista Enlazada (LeetCode 707)

Diseñar una lista enlazada desde cero requiere implementar sus operaciones fundamentales como añadir, obtener y eliminar nodos en varias posiciones. Para garantizar la coherencia y simplificar el código, es una práctica recomendada el uso de un nodo centinela (dummy head) como punto de partida para todas las operaciones, ya que evita el manejo especial del primer nodo.

La implementación de la clase MyLinkedList incluirá:

• Un nodo centinela (headSentinel) que siempre existe y su next apunta al primer nodo real de la lista.
• Un contador de tamaño (listSize) para mantener un registro eficiente del número de elementos.

class MyLinkedList {
private:
    // Definición de la estructura de un nodo de la lista
    struct Node {
        int val;
        Node* next;
        Node(int value) : val(value), next(nullptr) {}
    };

    Node* headSentinel; // El nodo centinela que siempre apunta a la cabeza de la lista
    int listSize;       // El tamaño actual de la lista

public:
    // Constructor: inicializa la lista con un nodo centinela
    MyLinkedList() {
        headSentinel = new Node(0); // El valor del centinela es arbitrario
        listSize = 0;
    }

    // Obtener el valor del nodo en un índice específico
    int get(int index) {
        if (index < 0 || index >= listSize) { // Validar que el índice esté dentro del rango
            return -1; // Retornar -1 si el índice no es válido
        }
        Node* current = headSentinel->next; // Empezar desde el primer nodo real
        for (int i = 0; i < index; ++i) {
            current = current->next; // Moverse al siguiente nodo
        }
        return current->val; // Retornar el valor del nodo en el índice
    }

    // Añadir un nodo al principio de la lista
    void addAtHead(int val) {
        Node* newNode = new Node(val);
        newNode->next = headSentinel->next; // El nuevo nodo apunta al antiguo primer nodo
        headSentinel->next = newNode;       // El centinela apunta al nuevo nodo
        listSize++;
    }

    // Añadir un nodo al final de la lista
    void addAtTail(int val) {
        Node* current = headSentinel;
        while (current->next != nullptr) { // Recorrer hasta el último nodo
            current = current->next;
        }
        Node* newNode = new Node(val);
        current->next = newNode; // El último nodo apunta al nuevo nodo
        listSize++;
    }

    // Añadir un nodo en un índice específico
    void addAtIndex(int index, int val) {
        if (index < 0 || index > listSize) { // Validar el índice, 'index == listSize' es válido para añadir al final
            return;
        }
        Node* current = headSentinel;
        for (int i = 0; i < index; ++i) { // Moverse hasta el nodo anterior a la posición de inserción
            current = current->next;
        }
        Node* newNode = new Node(val);
        newNode->next = current->next; // El nuevo nodo apunta al siguiente del 'current'
        current->next = newNode;       // 'current' apunta al nuevo nodo
        listSize++;
    }

    // Eliminar un nodo en un índice específico
    void deleteAtIndex(int index) {
        if (index < 0 || index >= listSize) { // Validar el índice
            return;
        }
        Node* current = headSentinel;
        for (int i = 0; i < index; ++i) { // Moverse hasta el nodo anterior al que se va a eliminar
            current = current->next;
        }
        Node* nodeToDelete = current->next;
        current->next = nodeToDelete->next; // Saltar el nodo a eliminar
        delete nodeToDelete; // Liberar la memoria
        listSize--;
    }

    // Destructor: libera la memoria de todos los nodos de la lista
    ~MyLinkedList() {
        Node* current = headSentinel;
        while (current != nullptr) {
            Node* nextNode = current->next;
            delete current;
            current = nextNode;
        }
    }
};

Inversión de una Lista Enlazada (LeetCode 206)

La inversión de una lista enlazada es un problema clásico que se puede resolver de forma iterativa o recursiva. Ambas aproximaciones tienen una complejidad temporal de O(N), donde N es el número de nodos en la lista, ya que cada nodo se visita y sus punteros se modifican una cantidad constante de veces.

Método 1: Iterativo (Dos Punteros)

Este método emplea tres punteros clave para gestionar la inversión de los enlaces durante el recorrido de la lista:

• previousNode: Este puntero rastrea el nodo que ha sido procesado y ya forma parte de la lista invertida. Inicialmente, se establece en nullptr, ya que el primer nodo de la lista invertida no tiene un predecesor.
• currentNode: Apunta al nodo que se está procesando en la iteración actual. Comienza en la cabeza de la lista original.
• nextNodeTemp: Una variable temporal crucial que se usa para guardar una referencia al siguiente nodo de currentNode antes de que el puntero currentNode->next sea modificado para invertir su dirección.

El algoritmo funciona de la siguiente manera:

1. Se inicia un bucle que continúa mientras currentNode no sea nullptr, es decir, mientras no se haya recorrido toda la lista.
2. Dentro del bucle, se guarda el siguiente nodo de currentNode en nextNodeTemp.
3. Se invierte el enlace: currentNode->next se actualiza para que apunte a previousNode.
4. previousNode se avanza, tomando el valor actual de currentNode.
5. currentNode se avanza, tomando el valor guardado en nextNodeTemp.
6. Al finalizar el bucle, previousNode contendrá la referencia a la nueva cabeza de la lista invertida.

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* previousNode = nullptr; // El nodo que va antes del actual en la nueva lista invertida
        ListNode* currentNode = head;     // El nodo que estamos procesando actualmente

        while (currentNode != nullptr) {
            ListNode* nextNodeTemp = currentNode->next; // Guarda el siguiente nodo antes de cambiar el enlace
            currentNode->next = previousNode;           // Invierte el puntero 'next' del nodo actual
            previousNode = currentNode;                 // Mueve 'previousNode' un paso adelante
            currentNode = nextNodeTemp;                 // Mueve 'currentNode' un paso adelante
        }
        return previousNode; // 'previousNode' es ahora la cabeza de la lista invertida
    }
};

Método 2: Recursivo

La inversión recursiva se basa en el principio de que si podemos invertir el resto de la lista (desde el segundo nodo en adelante), entonces podemos simplemente adjuntar el nodo cabeza actual al final de esa sub-lista invertida. Esta aproximación es a menudo más concisa, aunque puede ser conceptualmente más compleja para quienes no están familiarizados con la recursión.

Una función auxiliar recursiva reverse(currentNode, previousNode) puede manejar la lógica:

• Caso Base: Si currentNode es nullptr, significa que hemos llegado al final de la lista original. En este punto, previousNode es la referencia al último nodo procesado, que se convierte en la nueva cabeza de la lista invertida. Por lo tanto, se retorna previousNode.
• Paso Recursivo:
  1. Se guarda el siguiente nodo de currentNode en nextNodeTemp.
  2. Se invierte el enlace del nodo actual: currentNode->next apunta a previousNode.
  3. Se realiza la llamada recursiva para el resto de la lista: reverse(nextNodeTemp, currentNode). Esta llamada invertirá la sub-lista que comienza en nextNodeTemp y conectará currentNode a ella, finalmente retornando la nueva cabeza de la lista completamente invertida.

class Solution {
public:
    // Función principal que inicia el proceso de inversión recursiva
    ListNode* reverseList(ListNode* head) {
        // La llamada inicial se realiza con la cabeza de la lista y nullptr como el nodo anterior
        return reverse(head, nullptr);
    }

private:
    // Función auxiliar recursiva para invertir la lista
    ListNode* reverse(ListNode* currentNode, ListNode* previousNode) {
        // Caso base: si el nodo actual es nullptr, hemos llegado al final de la lista.
        // 'previousNode' en este punto es la nueva cabeza de la lista invertida.
        if (currentNode == nullptr) {
            return previousNode;
        }

        // Guarda el siguiente nodo antes de modificar el enlace del nodo actual
        ListNode* nextNodeTemp = currentNode->next;

        // Invierte el enlace del nodo actual: apunta al nodo anterior
        currentNode->next = previousNode;

        // Llama recursivamente a la función para procesar el resto de la lista.
        // 'nextNodeTemp' se convierte en el nuevo 'currentNode'.
        // 'currentNode' actual se convierte en el nuevo 'previousNode' para la siguiente llamada.
        return reverse(nextNodeTemp, currentNode);
    }
};