Solución de Palindrome Linked List

Clase 14 de 41 • Curso de Algoritmos Avanzados: Estructuras de Datos Lineales

Contenido del curso

Introducción

1
¿Ya tomaste el Curso Avanzado de Algoritmos: Patrones de Arrays y Strings?
00:52 min

Lista Enlazada

Pilas y colas

Colas de prioridad

Próximos pasos

41
Toma el Curso Avanzado de Algoritmos: Grafos y Árboles
00:33 min

Tomar examen

Comentarios

Nicolas Alpargatero

student•

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.

Nicolas Guillen

student•

🤯🤯🤯 que dicha que vi la clase porque no se me hubiera ocurrido en medio de una entrevista

Benjamin Rodriguez

student•

ya se, este tipo de aprendizajes hacen que el curso valga la pena :)

Irving Juárez

student•

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

Miguel Angel Reyes Moreno

student•

solución en typescript:

import { ListNode } from "./ListNode";
function isPalindrome(*head*: ListNode | null): boolean {    if (!*head* || !*head*.next) return true;
&#x20;   let slow = *head*;    let fast = *head*;
&#x20;   while (fast !== null && fast.next !== null) {        slow = slow.next!;        fast = fast.next.next!;    }
&#x20;   let prev: ListNode | null = null;    let current = slow;
&#x20;   *//\* reversing the second half of the list*    while (current !== null) {        let nextNode = current.next;        current.next = prev;        prev = current;        current = nextNode!;    }
&#x20;   let firstHalf = *head*;    let secondHalf = prev;
&#x20;   while (secondHalf !== null) {        if (firstHalf.val !== secondHalf.val) {            return false;        }        firstHalf = firstHalf.next!;        secondHalf = secondHalf.next!;    }
&#x20;   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));

Juan Pablo Reina Gutierrez

student•

Esta es mi solución:

Juan Pablo Reina Gutierrez

student•

Tuve un error en la línea 159, sería el código "while (primeraMitad != comSegMitad && segundaMitad != null)"

import { ListNode } from "./ListNode";
function isPalindrome(*head*: ListNode | null): boolean {    if (!*head* || !*head*.next) return true;
&#x20;   let slow = *head*;    let fast = *head*;
&#x20;   while (fast !== null && fast.next !== null) {        slow = slow.next!;        fast = fast.next.next!;    }
&#x20;   let prev: ListNode | null = null;    let current = slow;
&#x20;   *//\* reversing the second half of the list*    while (current !== null) {        let nextNode = current.next;        current.next = prev;        prev = current;        current = nextNode!;    }
&#x20;   let firstHalf = *head*;    let secondHalf = prev;
&#x20;   while (secondHalf !== null) {        if (firstHalf.val !== secondHalf.val) {            return false;        }        firstHalf = firstHalf.next!;        secondHalf = secondHalf.next!;    }
&#x20;   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));

Solución de Palindrome Linked List

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