Introducción

1

¬ŅYa tomaste el Curso Avanzado de Algoritmos: Patrones de Arrays y Strings?

Lista Enlazada

2

Estructura de datos: Lista Enlazada

3

Programando listas enlazadas con Java

4

Cómo Invertir una Lista Enlazada

5

Odd Even Linked List: an√°lisis del problema

6

Solución de Odd Even Linked List

7

Playground: Odd Even Liked List

8

Programando Odd Even Linked List con C++

9

Linked List Cycle: an√°lisis del problema

10

Solución de Linked List Cycle

11

Playground: Linked List Cycle

12

Programando Linked List Cycle con Python

13

Palindrome Linked List: an√°lisis del problema

14

Solución de Palindrome Linked List

15

Playground: Palindrome Linked List

16

Programando Palindrome Linked List con Java

17

Reorder List: an√°lisis del problema

18

Solución de Reorder List

19

Programando Reorder List con JavaScript

20

Playground: Reorder List Without Repeated Values

21

Reto: LRU Caché

22

Ejercicios recomendados de Lista Enlazada

23

Ejercicios resueltos de Lista Enlazada

Pilas y colas

24

Estructura de datos: Pilas y Colas

25

Paréntesis Válido: análisis del problema

26

Solución de Paréntesis Válido

27

Playground: Paréntesis Válido

28

Programando Paréntesis Válido con C++

29

Ejercicios recomendados de Pilas

Colas de prioridad

30

Estructura de datos: Colas de Prioridad

31

K Closest Points to Origin: an√°lisis del problema

32

Solución de K Closest Points to Origin

33

Playground: K Closest Points to Origin

34

Programando K Closest Points to Origin con Python

35

Reorganize String: an√°lisis del problema

36

Solución de Reorganize String

37

Playground: Reorganize String

38

Programando Reorganize String con Python

39

Ejercicios recomendados de Colas de prioridad

40

Ejercicios resueltos de Colas de prioridad

Próximos pasos

41

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

Aprende Inglés, Programación, AI, Ciberseguridad y más a precio especial.

Antes: $249

Currency
$209
Suscríbete

Termina en:

1 Días
23 Hrs
36 Min
27 Seg

Programando Palindrome Linked List con Java

16/41
Recursos

Aportes 8

Preguntas 1

Ordenar por:

¬ŅQuieres ver m√°s aportes, preguntas y respuestas de la comunidad?

La profe tuvo un error en la línea 11 al pasar el parámetro para la función de reversar porque se debe reversar es a partir de la segunda mitad, es decir quedaría algo así: "Nodo comienzoSegundaMitad = reversarLista(finPrimeraMitad.siguiente)".

En javascript:
con el puntero lento voy guardando los valores en una pila/stack
cuando llego a la mitad hay dos casos, que sea par o impar.
si es par, el lento avanza 1 y si es par el lento avanza 2 para comenzar a comparar los valores de la pila.
recorro lo que queda de lista sacando los valores de la pila.
devuelve falso si los valores son distintos, o si quedan elementos en la pila.
devuelve verdadero de lo contrario

function isPalindrome(cabeza) {

  if ( cabeza === null ||
    cabeza.siguiente === null || 
    cabeza.siguiente.siguiente === null) {
  return True;
  }

  let stack = [];
  stack.push(cabeza.valor);
  let lento = cabeza;
  let rapido = cabeza.siguiente.siguiente;

  while (rapido != null &&
    rapido.siguiente != null) {
    rapido = rapido.siguiente.siguiente;
    lento = lento.siguiente;
    stack.push(lento.valor);
  }
  if (rapido == null) {
    console.log("even list");
    lento = lento.siguiente
  }
  else {
    console.log("odd list");
    lento = lento.siguiente.siguiente;
  }
    
  while (lento != null){
    if (lento.valor != stack.pop())
      return false;
    
    lento = lento.siguiente;
  }

  if (stack.length != 0){
    return false;
  }
  return true;
}

codigo para probar

//a b c b a
const nodo1 = new Nodo("a");
const nodo2 = new Nodo("b"); 
const nodo3 = new Nodo("c");
const nodo4 = new Nodo("b");
const nodo5 = new Nodo("a");
nodo1.siguiente = nodo2;
nodo2.siguiente = nodo3;
nodo3.siguiente = nodo4;
nodo4.siguiente = nodo5;

console.log(isPalindrome(nodo1));

// a b b a
const node1 = new Nodo("a");
const node2 = new Nodo("b");  
const node3 = new Nodo("b");
const node4 = new Nodo("a");

node1.siguiente = node2; 
node2.siguiente = node3;
node3.siguiente = node4;
console.log(isPalindrome(node1));

simplemente por legibilidad espalindromo lo convertiria en una funcion

Un resultado similar se puede alcanzar utilizando una Queue y un Stack. Se recorre la lista enlazada O(n) y se almacenan los valores, uno por uno, en el Stack y en la Queue, luego, se recorren al tiempo comparando los valores. No obstante, este procedimiento ocupa un espacio auxiliar de O(n+n) de las otras estructuras. El algortimo que se propone en esta clase tiene la ventaja de ser "in-place", por lo que no requirre de más espacio temporal, sin embargo, hay algunos errores en la implementación, se pueden corregir facilmente con: Cambiar `Nodo comienzoSegundaMitad = reversarLista(cabeza);` Por: `Nodo comienzoSegundaMitad = reversarLista(finPrimeraMitad.siguiente);` En `public Nodo reversarLista(Nodo cabeza);` Retornar `return anterior;`

Ejecución con C++

template<class T>
bool Lista<T>::Palindrome() {
    // Defino mis punteros din√°micos
    Nodo<T> *lento = inicio;
    Nodo<T> *rapido = inicio;
    Nodo<T> *anterior = nullptr;
    Nodo<T> *actual = nullptr;
    Nodo<T> *medio = nullptr;
    Nodo<T> *auxiliar = nullptr;

    if (inicio == nullptr) {
        throw 404; // Lista vacía
    }

    // Mover los punteros lento y r√°pido
    while (rapido != nullptr && rapido->getSiguiente() != nullptr) {
        rapido = rapido->getSiguiente()->getSiguiente();
        anterior = lento;
        lento = lento->getSiguiente();
    }

    // Si rapido no es nulo, la lista tiene un n√ļmero impar de elementos, avanzar lento
    if (rapido != nullptr) {
        lento = lento->getSiguiente();
    }

    // Invertir la segunda mitad de la lista
    actual = lento;
    anterior = nullptr;
    while (actual != nullptr) {
        auxiliar = actual->getSiguiente();
        actual->setSiguiente(anterior);
        anterior = actual;
        actual = auxiliar;
    }

    // Comparar la primera mitad con la segunda mitad invertida
    medio = anterior;
    actual = inicio;
    while (medio != nullptr) {
        if (medio->getDato() != actual->getDato()) {
            return false; // No es un palíndromo
        }
        medio = medio->getSiguiente();
        actual = actual->getSiguiente();
    }

    return true; // Es un palíndromo
}

Inmutabilidad!!!

En Python.
Me faltaba el guardar la Lista inicial, creí que no se modificaba, pero al imprimir, efectivamente sí.
.
Una opción y sencilla es import copy y usar copy.deepcopy(cabeza) para que esta sea la que se cambie y no la original.

.
O otra opción:

def copyList(cabeza):
    if cabeza is None:
        return None
    copia = Nodo(cabeza.valor)
    copia.siguiente = copyList(cabeza.siguiente)
    return copia

.
Por cierto, el c√≥digo de los recursos est√° un poco diferente al de la clase. Pero creo que es solo el return de la function reversarLista en la clase esta como anterior, y en el archivo como actual. Y seg√ļn la implementaci√≥n de clases pasadas si es anteror.

Mi solución en JS.
Tomar en cuenta que aquí se esta creando tanto la clase Nodo, como la clase LinkedList y además unas funciones de utilería para poder acceder a cada uno de los Nodos después de haber creado la LinkedList.

function forEachNode(linkedList, callback) {
  let current = linkedList.head;
  callback(current);

  while (current.next) {
    current = current.next;
    callback(current);
  }
}

class Node {
  constructor(element) {
    this.element = element;
    this.next = null;
  }
}

class LinkedList {
  constructor(...items) {
    this.head = null;
    items.forEach((item) => this.add(new Node(item)));
  }

  add(node) {
    if (!this.head) {
      this.head = node;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }
  }
}

function isLinkedLinkPalindrome(linkedList) {
  let shortPointer = linkedList.head;
  let largePointer = linkedList.head;
  const firstHalf = [shortPointer.element];

  while (largePointer.next && largePointer.next.next) {
    firstHalf.unshift(shortPointer.next.element);
    shortPointer = shortPointer.next;
    largePointer = largePointer.next.next;
  }

  let currentComparisonItem;
  if (!largePointer.next) { // linkedList is odd
    currentComparisonItem = shortPointer;
  } else { // linkedList is even
    currentComparisonItem = shortPointer.next;
  }

  let counter = 0;
  while (currentComparisonItem) {
    if (firstHalf[counter] !== currentComparisonItem.element) return false;

    counter++;
    currentComparisonItem = currentComparisonItem.next;
  }

  return true;
}

const myLinkedList = new LinkedList(6,5,4,4,5,6);
console.log(isLinkedLinkPalindrome(myLinkedList));