Programando Palindrome Linked List con Java

Clase 16 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

Juan Pablo Reina Gutierrez

student•

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)".

Juan Pablo Reina Gutierrez

student•

¿Si reversamos dos veces la mitad de la lista como se muestra en la clase, esto no aumentaría la complejidad del algoritmo a O(n^2)?

Luis Lazcano

student•

No, n^2 significa que cada elemento se itera contra todos los elementos como en Bubble sort. En este caso solo se recorre la lista 2 veces en realidad solo la mitad. En todo caso sería 2 * (n /2) lo que al final daría solo O(n).

Lo que daría una complejidad a todo el problema de O(2n) lo que en la práctica es O(n)

Emilio Sala

student•

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));

Irving Juárez

student•

Yo hice algo similar a lo que mencionas, aunque creo que es mucho más limpio si se hace como tal una clase para Nodo y una para LinkedList

Reinaldo Mendoza

student•

simplemente por legibilidad espalindromo lo convertiria en una funcion

Mario Velandia

student•

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);

public Nodo reversarLista(Nodo cabeza);

Retornar return anterior;

Nicolas Lopez

student•

Mi solucion en Java:

package practice;

public class PalindromeValidationList {

    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(9);
        head.next.next = new Node(9);
        head.next.next.next = new Node(8);
        head.next.next.next.next = new Node(9);
        head.next.next.next.next.next = new Node(9);
        head.next.next.next.next.next.next = new Node(1);

        /*Node head = new Node(1);
        head.next = new Node(9);
        head.next.next = new Node(9);
        head.next.next.next = new Node(1);*/

        System.out.println(validatePalindrome(head));
    }

    public static boolean validatePalindrome(Node head) {
        if (head == null || head.next == null) { return false; }//If head is null, I don't have anything to validate.

        Node headBackUp = head;
        Node mid = findMid(head);

        Node reversedHeadList = reverseHalfRightList(mid);

        while (headBackUp != mid.next) {
            if (headBackUp.data != reversedHeadList.data) {
                return false;
            }
            headBackUp = headBackUp.next;
            reversedHeadList = reversedHeadList.next;
        }
        return true;
    }

    public static Node reverseHalfRightList(Node head) {
        if (head == null || head.next == null) { return head; }
        Node prev = null;
        Node curr = head;
        while (curr != null) {
            Node next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    public static Node findMid(Node head) {
        Node slow = head;
        Node fast = head.next;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

John Eduard Meneses González

student•

My solution!!

Francisco Roberto Gomez

student•

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
}

Reinaldo Mendoza

student•

Inmutabilidad!!!

Nicolas Alpargatero

student•

++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.

Irving Juárez

student•

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));

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;
}

//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));

package practice;

public class PalindromeValidationList {

    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(9);
        head.next.next = new Node(9);
        head.next.next.next = new Node(8);
        head.next.next.next.next = new Node(9);
        head.next.next.next.next.next = new Node(9);
        head.next.next.next.next.next.next = new Node(1);

        /*Node head = new Node(1);
        head.next = new Node(9);
        head.next.next = new Node(9);
        head.next.next.next = new Node(1);*/

        System.out.println(validatePalindrome(head));
    }

    public static boolean validatePalindrome(Node head) {
        if (head == null || head.next == null) { return false; }//If head is null, I don't have anything to validate.

        Node headBackUp = head;
        Node mid = findMid(head);

        Node reversedHeadList = reverseHalfRightList(mid);

        while (headBackUp != mid.next) {
            if (headBackUp.data != reversedHeadList.data) {
                return false;
            }
            headBackUp = headBackUp.next;
            reversedHeadList = reversedHeadList.next;
        }
        return true;
    }

    public static Node reverseHalfRightList(Node head) {
        if (head == null || head.next == null) { return head; }
        Node prev = null;
        Node curr = head;
        while (curr != null) {
            Node next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    public static Node findMid(Node head) {
        Node slow = head;
        Node fast = head.next;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

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
}

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));

Programando Palindrome Linked List con Java

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