Segundo día

Lista enlazada (fácil)

Oferta de espada 06. Imprimir lista en orden inverso

Dado el nodo cabeza de una lista enlazada, devuelve los valores de cada nodo en orden inverso (devolviéndolos como un array).

Ejemplo 1:

Entrada: cabeza = [1,3,2]
Salida: [2,3,1]

Restricciones:

0 <= longitud de la lista <= 10000

Enfoque de solución: pila auxiliar, relleno inverso, recursión

Pila auxiliar: Utiliza la propieadd de LIFO de la pila para lograr la inversión de nodos.

/**
 * Definición para lista enlazada simple.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        Stack<ListNode> stack = new Stack<ListNode>();
        ListNode temp = head;
        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }
        int size = stack.size();
        int[] print = new int[size];
        for (int i = 0; i < size; i++) {
            print[i] = stack.pop().val;
        }
        return print;
    }
}

Relleno inverso: Rellena los índices del array en orden inverso

/**
 * Definición para lista enlazada simple.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        ListNode currNode = head;
        int len = 0;
        while (currNode != null) {
            len ++;
            currNode = currNode.next;
        }
        int[] print = new int[len];
        
        for (int i = len-1; i >= 0; i --) {
            print[i] = head.val;
            head = head.next;
        }
        return print;
    }
}

Recursión: Utiliza la recursión para llegar al último nodo de la lista

/**
 * Definición para lista enlazada simple.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        ArrayList<Integer> tmp = new ArrayList<Integer>();
        recur(head, tmp);
        int[] res = new int[tmp.size()];
        for(int i = 0; i < res.length; i++)
            res[i] = tmp.get(i);
        return res;
    }
    void recur(ListNode head, ArrayList<Integer> tmp) {
        if(head == null) return;
        recur(head.next, tmp);
        tmp.add(head.val);
    }
}

Oferta de espada 24. Invertir lista enlazada

Define una función que recibe el nodo cabeza de una lista enlazada y la invierte, devolviendo el nodo cabeza de la lista invertida.

Ejemplo:

Entrada: 1->2->3->4->5->NULL
Salida: 5->4->3->2->1->NULL

Restricciones:

0 <= número de nodos <= 5000

Enfoque de solución: pila auxiliar, recursión, iteración

Pila auxiliar: Usa la característica de LIFO de la pila para invertir la lista enlazada

/**
 * Definición para lista enlazada simple.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode curr = head;
        Stack<ListNode> stack = new Stack<>();
        while (curr != null) {
            stack.push(curr);
            curr = curr.next;
        }
        ListNode listNode = stack.pop();
        ListNode res = listNode;
        while (!stack.isEmpty()) {
            listNode.next = stack.pop();
            listNode = listNode.next;
            listNode.next = null;
        }
        return res;
    }
}

Recursión: Usa la recursión con la pila del sistema para invertir la lista enlazada, terminando cuando llega al último nodo, realizando el intercambio head.next.next = head durante el proceso

/**
 * Definición para lista enlazada simple.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

Iteración: Reconstruye la lista usando el método de inserción frontal

/**
 * Definición para lista enlazada simple.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            // Guardar el siguiente nodo
            ListNode next = curr.next;
            // Cambiar la dirección del nodo
            curr.next = prev;
            // Guardar el nodo actual como cabeza
            prev = curr;
            // Acceder al siguiente nodo
            curr = next;
        }
        return prev;
    }
}

Los problemas de inversión de listas enlazadas no se limitan a este. Actualmente también se examinan frecuentemente inversiones de intervalos, múltiples inversiones de intervalos, etc.

92. Invertir lista enlazada II

Dado el puntero cabeza de una lista enlazada simple y dos enteros left y right, donde left <= right. Invierte los nodos de la lista desde la posición left hasta la posición right, y devuelve la lista invertida.

Ejemplo 1:

Entrada: cabeza = [1,2,3,4,5], left = 2, right = 4
Salida: [1,4,3,2,5]

Ejemplo 2:

Entrada: cabeza = [5], left = 1, right = 1
Salida: [5]

Condiciones:

• Número de nodos en la lista es n
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

Mejora: ¿Puedes hacerlo con una sola pasada?

Enfoque de solución: dos recorridos, un solo recorrido

Dos recorridos: Primero corta la lista, luego invierte la parte central, y finalmente reconecta la lista

/**
 * Definición para lista enlazada simple.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // Usar un nodo ficticio adicional
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;

        // Obtener el nodo anterior al índice izquierdo
        for (int i = 0; i < left-1; i ++) {
            pre = pre.next;
        }

        // Obtener el nodo derecho
        ListNode rightNode = pre;
        for (int i = 0; i < right-left+1; i ++) {
            rightNode = rightNode.next;
        }

        // Cortar la lista
        ListNode leftNode = pre.next;

        // Guardar el nodo posterior a rightNode
        ListNode curr = rightNode.next;

        // Cortar la conexión
        pre.next = null;
        rightNode.next = null;

        // Invertir la lista
        reverseLinkedList(leftNode);

        // Reconectar
        pre.next = rightNode;
        leftNode.next = curr;
        return dummyNode.next;
    }
    // Invertir lista
    private void reverseLinkedList(ListNode head) {
        ListNode curr = head;
        ListNode pre = null;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
    }
}

Complejidad: Tiempo O(n) Espacio O(1)

Un solo recorrido: Usar el método de inserción frontal para completar la inversión

/**
 * Definición para lista enlazada simple.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;
        for (int i = 0; i < left - 1; i ++) {
            pre = pre.next;
        }
        ListNode curr = pre.next;
        // Pasos memorizados
        for (int i = 0; i < right-left; i ++) {
            // Guardar el siguiente nodo
            ListNode next = curr.next;
            // Cambiar el puntero del nodo actual
            curr.next = next.next;
            // Cambiar el puntero del nodo next
            next.next = pre.next;
            // Cambiar el puntero del nodo pre
            pre.next = next;
        }
        return dummyNode.next;

    }
}

Complejidad: Tiempo O(n) Espacio O(1)

25. Invertir lista enlazada en grupos de k elementos

Dada una lista enlazada, invierte los nodos agrupándolos de k en k. Devuelve la lista invertida.

k es un entero positivo, su valor es menor o igual a la longitud de la lista.

Si el número total de nodos no es múltiplo de k, los nodos restantes deben mantenerse en su orden original.

Mejora:

• ¿Puedes diseñar un algoritmo que use solo espacio extra constante?
• No puedes cambiar solo los valores internos de los nodos, sino que debes realizar intercambios reales de nodos.

Ejemplo 1:

Entrada: cabeza = [1,2,3,4,5], k = 2
Salida: [2,1,4,3,5]

Ejemplo 2:

Entrada: cabeza = [1,2,3,4,5], k = 3
Salida: [3,2,1,4,5]

Ejemplo 3:

Entrada: cabeza = [1,2,3,4,5], k = 1
Salida: [1,2,3,4,5]

Ejemplo 4:

Entrada: cabeza = [1], k = 1
Salida: [1]

Condiciones:

• Número de nodos en la lista está en el rango sz
• 1 <= sz <= 5000
• 0 <= Node.val <= 1000
• 1 <= k <= sz

Enfoque de solución: múltiples inversiones de intervalos

Múltiples inversiones de intervalos:

/**
 * Definición para lista enlazada simple.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        // pre representa el predecesor de la lista por invertir
        ListNode pre = dummyNode;
        // end representa el final de la lista por invertir
        ListNode end = dummyNode;
        while (end.next != null) {
            for (int i = 0; i < k && end != null; i ++) {
                end = end.next;
            }
            if (end == null) {
                break;
            }
            // La inversión de intervalos es similar, guardar los nodos antes de la inversión, luego reconectarlos
            ListNode start = pre.next;
            ListNode next = end.next;
            end.next = null;
            pre.next = reverse(start);
            start.next = next;
            pre = start;
            end = pre;

        }
        return dummyNode.next;
    }
    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }

}

Complejidad: Tiempo O(n) Espacio O(1)

Oferta de espada 35. Copiar lista compleja

Implementa la función copyRandomList para copiar una lista compleja. En una lista compleja, cada nodo tiene un puntero next que apunta al siguiente nodo, además de un puntero random que puede apuntar a cualquier nodo de la lista o a null.

Ejemplo 1:

Entrada: cabeza = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Salida: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Ejemplo 2:

Entrada: cabeza = [[1,1],[2,1]]
Salida: [[1,1],[2,1]]

Ejemplo 3:

Entrada: cabeza = [[3,null],[3,0],[3,null]]
Salida: [[3,null],[3,0],[3,null]]

Ejemplo 4:

Entrada: cabeza = []
Salida: []
Explicación: La lista dada está vacía (puntero nulo), por lo tanto devuelve null.

Condiciones:

• -10000 <= Node.val <= 10000
• Node.random es null o apunta a un nodo de la lista.
• El número de nodos no supera los 1000.

Enfoque de solución: copia con tabla hash, descomposición de nodos

Copia con tabla hash: Usa HashMap para almacenar todos los nodos primero, luego reconstruye la lista

/*
// Definición para un nodo.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return head;
        }
        // clave almacena el nodo original, valor almacena el nodo a copiar
        Map<Node, Node> map = new HashMap<>();
        // Copiar valores de los nodos
        for (Node cur = head; cur != null; cur = cur.next) {
            map.put(cur, new Node(cur.val));
        }
        // Recorrer la lista, usar la información del nodo original para llenar los campos next y random del nodo copiado
        for (Node cur = head; cur != null; cur = cur.next) {
            // Extraer y asignar
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
        }
        return map.get(head);
    }
}

Complejidad: Tiempo O(n) Espacio O(n)

Descomposición de nodos: Crea un nodo idéntico en la posición siguiente a cada nodo original, primero copia los campos next y val, luego recorre una vez para copiar el campo random, finalmente separa las dos listas

/*
// Definición para un nodo.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }

        Node cur = head;
        // 1. Copiar cada nodo y construir una lista concatenada
        while(cur != null) {
            Node tmp = new Node(cur.val);
            tmp.next = cur.next;
            cur.next = tmp;
            cur = tmp.next;
        }
        // 2. Establecer el puntero random de los nuevos nodos
        cur = head;
        while(cur != null) {
            if(cur.random != null)
                cur.next.random = cur.random.next;
            cur = cur.next.next;
        }
        // 3. Separar las dos listas
        cur = head.next;
        Node pre = head, res = head.next;
        while(cur.next != null) {
            pre.next = pre.next.next;
            cur.next = cur.next.next;
            pre = pre.next;
            cur = cur.next;
        }
        pre.next = null; // Manejar el último nodo de la lista original por separado
        return res;      // Devolver el nodo cabeza de la nueva lista
    }
}

Complejiadd: Tiempo O(n) Espacio O(1)