Esto si es enseñar lógica, tremendo. Aunque esperaba mejor Big O, aunque sea la misma Big O realmente si hace menos interacción, haciéndolo más óptimo. Interesante.
Introducción
¿Ya tomaste el Curso Avanzado de Algoritmos: Patrones de Arrays y Strings?
Lista Enlazada
Estructura de datos: Lista Enlazada
Programando listas enlazadas con Java
Cómo Invertir una Lista Enlazada
Odd Even Linked List: análisis del problema
Solución de Odd Even Linked List
Playground: Odd Even Liked List
Programando Odd Even Linked List con C++
Linked List Cycle: análisis del problema
Solución de Linked List Cycle
Playground: Linked List Cycle
Programando Linked List Cycle con Python
Palindrome Linked List: análisis del problema
Solución de Palindrome Linked List
Playground: Palindrome Linked List
Programando Palindrome Linked List con Java
Reorder List: análisis del problema
Solución de Reorder List
Programando Reorder List con JavaScript
Playground: Reorder List Without Repeated Values
Reto: LRU Caché
Ejercicios recomendados de Lista Enlazada
Ejercicios resueltos de Lista Enlazada
Pilas y colas
Estructura de datos: Pilas y Colas
Paréntesis Válido: análisis del problema
Solución de Paréntesis Válido
Playground: Paréntesis Válido
Programando Paréntesis Válido con C++
Ejercicios recomendados de Pilas
Colas de prioridad
Estructura de datos: Colas de Prioridad
K Closest Points to Origin: análisis del problema
Solución de K Closest Points to Origin
Playground: K Closest Points to Origin
Programando K Closest Points to Origin con Python
Reorganize String: análisis del problema
Solución de Reorganize String
Playground: Reorganize String
Programando Reorganize String con Python
Ejercicios recomendados de Colas de prioridad
Ejercicios resueltos de Colas de prioridad
Próximos pasos
Toma el Curso Avanzado de Algoritmos: Grafos y Árboles
No tienes acceso a esta clase
¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera
Si ya tienes una cuenta,
Solución de Palindrome Linked List
14/41Recursos
Aportes 5
Preguntas 0
Ordenar por:
🤯🤯🤯 que dicha que vi la clase porque no se me hubiera ocurrido en medio de una entrevista
solución en typescript:
```
import { ListNode } from "./ListNode";
function isPalindrome(*head*: ListNode | null): boolean { if (!*head* || !*head*.next) return true;
let slow = *head*; let fast = *head*;
while (fast !== null && fast.next !== null) { slow = slow.next!; fast = fast.next.next!; }
let prev: ListNode | null = null; let current = slow;
*//\* reversing the second half of the list* while (current !== null) { let nextNode = current.next; current.next = prev; prev = current; current = nextNode!; }
let firstHalf = *head*; let secondHalf = prev;
while (secondHalf !== null) { if (firstHalf.val !== secondHalf.val) { return false; } firstHalf = firstHalf.next!; secondHalf = secondHalf.next!; }
return true;};
const listNode: ListNode = new ListNode(1, new ListNode(2, new ListNode(2, new ListNode(1))));*//\* \[1,2,2,1] -> true*const listNode2: ListNode = new ListNode(1, new ListNode(2));*//\* \[1,2] -> false*
console.log(isPalindrome(listNode));console.log(isPalindrome(listNode2));
```
Esta es mi solución:
Estaba pensando que el “reversar” los nodos de la segunda mitad puede llegar a ser complejo. Una solución que yo creo pudiera ser un poco más sencillas es la siguiente:
- Utilizar los dos apuntadores (rápido y lento) hasta llegar a la mitad de la lista enlazada
- Por cada nuevo nodo del apuntador lento, se estaría llenando un array, donde cada nuevo elemento se inserta al inicio de este array. En el caso del ejemplo, el array empieza como [1] y a la segunda iteración [9,1]
- Una vez que se haya llegado a la mitad, el apuntador rápido comienza a actuar de la misma manera que el lento (avanzando un nodo a la vez) y el lento deja de avanzar.
- El apuntador rápido (que ya esta actuando como el lento) compara su nuevo valor con el del array creado por el del apuntador lento. De esta manera cuando algún valor no coincida, sabremos que no es un palindromo.
.
Creo que esta podría ser una solución más sencilla, aunque claramente sería más costosa en términos de Complejidad Espacial, ya que la solución que yo propongo tendría:
- Complejidad espacial de O(n)
- Complejidad temporal de O(n)
.
Mientras que la solución propuesta en la clase tendría
- Complejidad espacial de O(1)
- Complejidad temporal de O(n)
.
De cualquier forma creo que es un tradeoff que vale la pena tomar
¿Quieres ver más aportes, preguntas y respuestas de la comunidad?