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

Solución de Reorder List

Comentarios

REYNALDO FABIAN NORIEGA ZAMBRANO

student•

Aporte en C++:

Node * reorder_list(Node *list){

	if(!list) return nullptr;
	Node *head = list;
	Node *tail = list;
	Node *mid = head;
	Node *tmp;

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

	}
	tmp->next = nullptr;

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

	return head;
}

Carlos Hernandez

student•

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

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

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

    const maxLength = Math.max(leftHalf.length, rightHalf.length);

    for (let index = 0; index < maxLength; index++) {
        const currentLeft = leftHalf[index];
        const currentRight = rightHalf[rightHalf.length - 1 - index];
        currentLeft.siguiente = currentRight ? currentRight : null;

        if (currentRight) {
            currentRight.siguiente = leftHalf[index + 1] ? leftHalf[index + 1] : null;
        }
    }

    return leftHalf[0];
}

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


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

console.log(reorderList(nodo1).siguiente);
```class Nodo {    constructor(valor) {      this.valor = valor;      this.siguiente = null;    }  }  function reorderList(head) {    // Tu código aquí 👇    let slow = head, fast = head;    let leftHalf = \[slow];    let rightHalf = \[];
    while (fast.siguiente && fast.siguiente.siguiente) {        fast = fast.siguiente.siguiente;        slow = slow.siguiente;        leftHalf.push(slow);    }
    while (slow.siguiente) {        rightHalf.push(slow.siguiente);        slow = slow.siguiente;    }
    const maxLength = Math.max(leftHalf.length, rightHalf.length);
    for (let index = 0; index < maxLength; index++) {        const currentLeft = leftHalf\[index];        const currentRight = rightHalf\[rightHalf.length - 1 - index];        currentLeft.siguiente = currentRight ? currentRight : null;
        if (currentRight) {            currentRight.siguiente = leftHalf\[index + 1] ? leftHalf\[index + 1] : null;        }    }
    return leftHalf\[0];}
function clon(obj) {    return JSON.parse(JSON.stringify(obj));}

// Inputconst nodo1 = new Nodo("a");const nodo2 = new Nodo("b");const nodo3 = new Nodo("c");const nodo4 = new Nodo("d");nodo1.siguiente = nodo2;nodo2.siguiente = nodo3;nodo3.siguiente = nodo4;
console.log(reorderList(nodo1).siguiente);

Francisco Roberto Gomez

student•

Se me ocurre también una implementacion similar a Odd Even List teniendo 2 referencias fijas. Una para mi inicio y otra para la mitad. De esa forma ir intercalando los elementos.

Nicolas Alpargatero

student•

++Resultados en Python:++

Implementación:

lo que más me genero dificultad es que me entraba en infinite loop, y era por que me faltaba el middle.next = None y el current.next.next = next_node para que conecte con la primera lista.

Node * reorder_list(Node *list){

	if(!list) return nullptr;
	Node *head = list;
	Node *tail = list;
	Node *mid = head;
	Node *tmp;

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

	}
	tmp->next = nullptr;

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

	return head;
}

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

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

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

    const maxLength = Math.max(leftHalf.length, rightHalf.length);

    for (let index = 0; index < maxLength; index++) {
        const currentLeft = leftHalf[index];
        const currentRight = rightHalf[rightHalf.length - 1 - index];
        currentLeft.siguiente = currentRight ? currentRight : null;

        if (currentRight) {
            currentRight.siguiente = leftHalf[index + 1] ? leftHalf[index + 1] : null;
        }
    }

    return leftHalf[0];
}

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


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

console.log(reorderList(nodo1).siguiente);
```class Nodo {    constructor(valor) {      this.valor = valor;      this.siguiente = null;    }  }  function reorderList(head) {    // Tu código aquí 👇    let slow = head, fast = head;    let leftHalf = \[slow];    let rightHalf = \[];
    while (fast.siguiente && fast.siguiente.siguiente) {        fast = fast.siguiente.siguiente;        slow = slow.siguiente;        leftHalf.push(slow);    }
    while (slow.siguiente) {        rightHalf.push(slow.siguiente);        slow = slow.siguiente;    }
    const maxLength = Math.max(leftHalf.length, rightHalf.length);
    for (let index = 0; index < maxLength; index++) {        const currentLeft = leftHalf\[index];        const currentRight = rightHalf\[rightHalf.length - 1 - index];        currentLeft.siguiente = currentRight ? currentRight : null;
        if (currentRight) {            currentRight.siguiente = leftHalf\[index + 1] ? leftHalf\[index + 1] : null;        }    }
    return leftHalf\[0];}
function clon(obj) {    return JSON.parse(JSON.stringify(obj));}

// Inputconst nodo1 = new Nodo("a");const nodo2 = new Nodo("b");const nodo3 = new Nodo("c");const nodo4 = new Nodo("d");nodo1.siguiente = nodo2;nodo2.siguiente = nodo3;nodo3.siguiente = nodo4;
console.log(reorderList(nodo1).siguiente);

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