Playground: Palindrome Linked List

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

REYNALDO FABIAN NORIEGA ZAMBRANO

student••

Mi aporte en C++:

#include<iostream>
#include<vector>


class Node{
public:
	int val;
	Node *next;
};


bool is_palindrome(Node *&list){

	if(!list) return false;
	int count = 1;
	Node *head = list;
	Node *tail = list;
	Node *mid = head;

	while(tail && tail->next){
		tail = tail->next->next;
		mid = mid->next;

		if(tail) count += 2;
		else count++;
	}

	//reverse the second half if the list
	Node *prev =  nullptr;
	Node *current = mid;
	if(count % 2) current = mid->next;
	while(current){
		Node *tmp = current->next;
		current->next = prev;
		prev = current;
		current = tmp;
	}

	//now compare both halves of the list
	current = prev;
	mid = head;
	while(current){
		if(mid->val != current->val){
			return false;
		}
		else{
			current =  current->next;
			mid = mid->next;
		}
	}

	return true;
}


int main(){

	std::vector<int> elems = {1,9,7,9,1};
	Node *head = new Node;
	Node *current = head;
	for(int e = 0;e<elems.size()-1;e++){
		current->val = elems[e];
		current->next =  new Node;
		current = current->next;
	}
	current->val = elems[elems.size()-1];
	current->next = nullptr;
	current = head;
	while(current){
		std::cout << current->val << std::endl;
		current = current->next;
	}
	
	if(is_palindrome(head)) std::cout << "it is palindrome" << std::endl;
	else std::cout << "it is not palindrome" << std::endl;

	return 0;
}

John Eduard Meneses González

student•

My Solution!!

Carlos Hernandez

student•

Mi solución:class Nodo { constructor(valor) { this.valor = valor; this.siguiente = null; } } function isPalindrome(head) { // Tu código aquí 👇 let slow = head, fast = head; let leftHalf = [slow.valor]; let rightHalf = []; while (fast.siguiente && fast.siguiente.siguiente) { fast = fast.siguiente.siguiente; slow = slow.siguiente; leftHalf.push(slow.valor); } while (slow.siguiente) { rightHalf.push(slow.siguiente.valor); slow = slow.siguiente; } rightHalf.reverse(); const minLength = Math.min(leftHalf.length, rightHalf.length); for (let index = 0; index < minLength; index++) { if (leftHalf[index] !== rightHalf[index]) return false; } return true;} function clon(obj) { return JSON.parse(JSON.stringify(obj));}

// Inputconst nodo1 = new Nodo("a");const nodo2 = new Nodo("b");const nodo3 = new Nodo("a");nodo1.siguiente = nodo2;nodo2.siguiente = nodo3; console.log(isPalindrome(nodo1));

class Nodo {
    constructor(valor) {
      this.valor = valor;
      this.siguiente = null;
    }
  }
  
function isPalindrome(head) {
    // Tu código aquí 👇
    let slow = head, fast = head;
    let leftHalf = [slow.valor];
    let rightHalf = [];

    while (fast.siguiente && fast.siguiente.siguiente) {
        fast = fast.siguiente.siguiente;
        slow = slow.siguiente;
        leftHalf.push(slow.valor);
    }

    while (slow.siguiente) {
        rightHalf.push(slow.siguiente.valor);
        slow = slow.siguiente;
    }

    rightHalf.reverse();

    const minLength = Math.min(leftHalf.length, rightHalf.length);

    for (let index = 0; index < minLength; index++) {
        if (leftHalf[index] !== rightHalf[index]) return false; 
    }

    return true;
}

function clon(obj) {
    return JSON.parse(JSON.stringify(obj));
}


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

console.log(isPalindrome(nodo1));

Miguel Angel Reyes Moreno

student•

mi solución:

export function isPalindrome(cabeza) {  if (!cabeza || !cabeza.siguiente)    return true;  var slow = cabeza;  var fast = cabeza;  while (fast !== null && fast.siguiente !== null) {    slow = slow.siguiente;    fast = fast.siguiente.siguiente;  }  var prev = null;  var current = slow;  //\* reversing the second half of the list  while (current !== null) {    var siguienteNode = current.siguiente;    current.siguiente = prev;    prev = current;    current = siguienteNode;  }  var firstHalf = cabeza;  var secondHalf = prev;  while (secondHalf !== null) {    if (firstHalf.valor !== secondHalf.valor) {      return false;    }    firstHalf = firstHalf.siguiente;    secondHalf = secondHalf.siguiente;  }  return true;}

Joan paredes yupanqui

student•

Rafael Estiven Uribe Álvarez

student•

Mi solución:

Nicolas Alpargatero

student•

En Python no fue necesario clonar, a una variable se le asigna la cabeza

def isPalindrome(cabeza):
    if not cabeza: return True
    p1 = cabeza
    p2 = reversarLista(encontrarMitad(p1))
    esPalindromo = True
    while esPalindromo and p2:
        if p1.valor != p2.valor:
            esPalindromo = False
        p1 = p1.siguiente
        p2 = p2.siguiente
    return esPalindromo

Nicolas Alpargatero

student•

Bueno aprendí que no es necesario pero que si se quiere usar la Linked List después si es necesario, lo explican en la siguiente clase 👀😅 y si ya lo probé 🫡

#include<iostream>
#include<vector>


class Node{
public:
	int val;
	Node *next;
};


bool is_palindrome(Node *&list){

	if(!list) return false;
	int count = 1;
	Node *head = list;
	Node *tail = list;
	Node *mid = head;

	while(tail && tail->next){
		tail = tail->next->next;
		mid = mid->next;

		if(tail) count += 2;
		else count++;
	}

	//reverse the second half if the list
	Node *prev =  nullptr;
	Node *current = mid;
	if(count % 2) current = mid->next;
	while(current){
		Node *tmp = current->next;
		current->next = prev;
		prev = current;
		current = tmp;
	}

	//now compare both halves of the list
	current = prev;
	mid = head;
	while(current){
		if(mid->val != current->val){
			return false;
		}
		else{
			current =  current->next;
			mid = mid->next;
		}
	}

	return true;
}


int main(){

	std::vector<int> elems = {1,9,7,9,1};
	Node *head = new Node;
	Node *current = head;
	for(int e = 0;e<elems.size()-1;e++){
		current->val = elems[e];
		current->next =  new Node;
		current = current->next;
	}
	current->val = elems[elems.size()-1];
	current->next = nullptr;
	current = head;
	while(current){
		std::cout << current->val << std::endl;
		current = current->next;
	}
	
	if(is_palindrome(head)) std::cout << "it is palindrome" << std::endl;
	else std::cout << "it is not palindrome" << std::endl;

	return 0;
}

class Nodo {
    constructor(valor) {
      this.valor = valor;
      this.siguiente = null;
    }
  }
  
function isPalindrome(head) {
    // Tu código aquí 👇
    let slow = head, fast = head;
    let leftHalf = [slow.valor];
    let rightHalf = [];

    while (fast.siguiente && fast.siguiente.siguiente) {
        fast = fast.siguiente.siguiente;
        slow = slow.siguiente;
        leftHalf.push(slow.valor);
    }

    while (slow.siguiente) {
        rightHalf.push(slow.siguiente.valor);
        slow = slow.siguiente;
    }

    rightHalf.reverse();

    const minLength = Math.min(leftHalf.length, rightHalf.length);

    for (let index = 0; index < minLength; index++) {
        if (leftHalf[index] !== rightHalf[index]) return false; 
    }

    return true;
}

function clon(obj) {
    return JSON.parse(JSON.stringify(obj));
}


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

console.log(isPalindrome(nodo1));

export function isPalindrome(cabeza) {  if (!cabeza || !cabeza.siguiente)    return true;  var slow = cabeza;  var fast = cabeza;  while (fast !== null && fast.siguiente !== null) {    slow = slow.siguiente;    fast = fast.siguiente.siguiente;  }  var prev = null;  var current = slow;  //\* reversing the second half of the list  while (current !== null) {    var siguienteNode = current.siguiente;    current.siguiente = prev;    prev = current;    current = siguienteNode;  }  var firstHalf = cabeza;  var secondHalf = prev;  while (secondHalf !== null) {    if (firstHalf.valor !== secondHalf.valor) {      return false;    }    firstHalf = firstHalf.siguiente;    secondHalf = secondHalf.siguiente;  }  return true;}

def isPalindrome(cabeza):
    if not cabeza: return True
    p1 = cabeza
    p2 = reversarLista(encontrarMitad(p1))
    esPalindromo = True
    while esPalindromo and p2:
        if p1.valor != p2.valor:
            esPalindromo = False
        p1 = p1.siguiente
        p2 = p2.siguiente
    return esPalindromo

Playground: 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

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 Prácticos con Listas Enlazadas y Historial de Navegador

Operaciones con Listas Enlazadas: Suma, Intercambio y Navegador

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

Comparación de Cadenas con Backspaces

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

Colas de Prioridad: Ejercicios Prácticos y Soluciones

Colas de Prioridad y Gestión de Eventos

Próximos pasos

Toma el Curso Avanzado de Algoritmos: Grafos y Árboles