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

Programando Reorder List con JavaScript

Comentarios

Nicolas Guillen

student•

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

student•

No tiene las listas pero tiene otros algoritmos:

Nicolas Alpargatero

student•

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

student•

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

student•

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

student•

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

Nicolas Guillen

student•

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

Hans Arias

student•

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

student•

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

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

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

}

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

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