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

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

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

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

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?

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

Programando Reorder List con JavaScript

Progreso del curso

Introducción

Lista Enlazada

Pilas y colas

Colas de prioridad

Próximos pasos