Playground: Palindrome Linked List

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

Playground: Palindrome Linked List

Todos los cursos GRATIS

Se acaba en:

00díasd:00hrsh:00minm:00segs

Comentarios7

REYNALDO FABIAN NORIEGA ZAMBRANO

Estudiante

Hace 8 meses•editado

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

Estudiante

Hace un año

My Solution!!

Carlos Hernandez

Estudiante

Hace 2 años

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

Estudiante

Hace 2 años

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

Estudiante

Hace 3 años

Rafael Estiven Uribe Álvarez

Estudiante

Hace 3 años

Mi solución:

Nicolas Alpargatero

Estudiante

Hace 3 años

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

Estudiante

Hace 3 años

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

Todos los cursos GRATIS