Programando Reorder List con JavaScript

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

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

Tomar examen

Cursos Empresas Blog Live Conf Eventos Precios

0:0016:45

Programando Reorder List con JavaScript

Curso de Algoritmos Avanzados: Estructuras de Datos Lineales

Clase 16 de 34

Clase 16 / 34

Comentarios (6)6 comentarios

Nicolas Guillen

Hace 3 años

Creo que la parte más dicífil, es mover los nodos "in-place" y siguir mentalmente qué tiene la variable temporal, sin perder la cabeza (no pun intended)

Hay alguna herramienta para visualiar la lista mientras va cambiando?

Miguel Angel Reyes Moreno

Hace 2 años

No tiene las listas pero tiene otros algoritmos:

Nicolas Alpargatero

El de la profe no me ejecutó como se esperaba, tal vez sea por la copia del head, aunque lo intente ese mismo código en python y no. En la clase pasada deje el ejercicio con python funcional.

Hans Arias

Me paso lo mismo en Java, creo lo que se debe es clonar, ya que si se copia el objecto guardado en una variable a otra, se afectara los cambios al original ya que hace referencia al objecto guardado en memoria, en el caso de Java existe una opciona de una interfaz clonable, creo que python deberia disponer una forma de hacerlo.

Esteban Maya

Esta fue mi solución para el reorder, se me complicó un poco las variables temporales que hay para reorganizar la linked list. Este fue hecho en python

def reorder(head):
  if not head or not head.next: return head
  slow = head
  fast = head
  while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
  reverse_part= reverse(slow)
  while head and reverse_part:
    temp = head.next
    head.next = reverse_part
    head = temp
    temp = reverse_part.next
    reverse_part.next = head
    reverse_part = temp
  return head

Cristian Camilo Vargas Peña

Probe con c#, me estaba generando un ciclo infinito en el ultimo while, pero creando una segunda variable temporal para p2 me funciono

Github Copilot 🤯 creo que no es tan eficiente y ocupa más memoria pero qué les parece esta respusta de la Ai?

Se me hizo dificil el ejercicio, luego encontrar la mitad y de reversar la segunda mitad del nodo, cree un metodo getSize(), para conocer su tamaño de la lista, adicionalmente, implemente una logica de par e impar en donde si es par agregaba el node la primera mitad en caso que no agregaba el node de la segunda mitad.

LinkedlistReorder.java

package org.example.reorder;

import org.example.Node;

public class LinkedListReorder {
    Node head;

    public void push (int data) {
        if (findNode(data) != null) {
            return;
        }

        Node node = new Node(data);
        node.next = head;
        head = node;
    }

    public void print () {
        Node temp = head;
        System.out.print("Numbers -> ");
        while (temp != null) {
            System.out.print(temp.data);
            temp = temp.next;
        }

        System.out.println();
    }

    private Node getHalf (Node node) {
        Node slow = node;
        Node fast = node;

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

        return slow;
    }

    private Node getNodeReversed (Node node) {
        Node prev = null;
        Node iteration = node.clone();

        while (iteration != null) {
            Node snapshot = iteration.next;
            iteration.next = prev;
            prev = iteration;
            iteration = snapshot;
        }

        return prev;
    }

    public Node findNode (int data) {
        if (head == null) return null;

        Node iteration = head.clone();
        while (iteration != null) {
            if (iteration.data == data) return iteration;

            iteration = iteration.next;
        }

        return null;
    }

    public int getSize () {
        Node iteration = head.clone();
        int count = 0;
        while (iteration != null) {
            count++;
            iteration = iteration.next;
        }

        return count;
    }

    public Node reorder () {
        Node copy = head.clone();

        if (copy == null) {
            return null;
        }

        Node secondHalfReserved = getNodeReversed(getHalf(copy).next);
        Node iteration = secondHalfReserved.clone();

        Node second = iteration.clone();
        Node first = copy.clone();

        Node composed = null;

        int count = getSize();

        for (int i = 1; i < count; i++) {
            Node aux;

            if (i % 2 == 0) {
                aux = second;
                second = second.next;
            } else {
                aux = first;
                first = first.next;
            }

            aux.next = composed;

            composed = aux;
        }

        return composed;
    }

}

Node.java

package org.example;

public class Node implements Cloneable{
    public int data;
    public Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }

    @Override
    public Node clone() {
        Node copy = null;

        try {
            copy = (Node) super.clone();
        }catch (CloneNotSupportedException e) {
            copy = new Node(this.data);
            copy.next = this.next;
        }

        return copy;
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", next=" + next +
                '}';
    }
}

Joan paredes yupanqui

En el resultado se ve que imprime la lisa original, luego el reoder list y si vuelvo a consultar la lista original, se puede ver que no ha sido afectada, porque estoy haciendolo en otra lista el reorder List, sin afectar la lista original

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

Programando Odd Even Linked List con C++

Linked List Cycle: análisis del problema

Solución de Linked List Cycle

Programando Linked List Cycle con Python

Palindrome Linked List: análisis del problema

Solución de 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

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

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

Programando K Closest Points to Origin con Python

Reorganize String: análisis del problema

Solución de 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

Programando Reorder List con JavaScript