Programa de Javascript para la división alterna de una lista dada de enlace único: conjunto 1

Escriba una función AlternatingSplit() que tome una lista y divida sus Nodes para hacer dos listas más pequeñas ‘a’ y ‘b’. Las sublistas deben estar hechas de elementos alternos en la lista original. Entonces, si la lista original es 0->1->0->1->0->1, entonces una sublista debería ser 0->0->0 y la otra debería ser 1->1->1.

Método (usando Nodes ficticios): 
aquí hay un enfoque que crea las sublistas en el mismo orden que la lista de origen. El código utiliza Nodes de encabezado ficticios temporales para las listas ‘a’ y ‘b’ a medida que se crean. Cada sublista tiene un puntero de «cola» que apunta a su último Node actual, de esa manera se pueden agregar fácilmente nuevos Nodes al final de cada lista. Los Nodes ficticios dan a los punteros de cola algo a lo que apuntar inicialmente. Los Nodes ficticios son eficientes en este caso porque son temporales y están asignados en la pila. Alternativamente, los «punteros de referencia» locales (que siempre apuntan al último puntero de la lista en lugar del último Node) podrían usarse para evitar los Nodes ficticios.

<script>
// Javascript program to implement the 
// above approach
function AlternatingSplit(source, aRef, 
                          bRef) 
{
    var aDummy = new Node();
  
    // Points to the last node in 'a' 
    var aTail = aDummy; 
    var bDummy = new Node();
  
    // Points to the last node in 'b' 
    var bTail = bDummy; 
    var current = source;
    aDummy.next = null;
    bDummy.next = null;
    while (current != null) 
    {
        // Add at 'a' tail 
        MoveNode((aTail.next), 
                  current); 
  
        // Advance the 'a' tail 
        aTail = aTail.next; 
        if (current != null) 
        {
            MoveNode((bTail.next), 
                      current);
            bTail = bTail.next;
        }
    }
    aRef = aDummy.next;
    bRef = bDummy.next;
}
// This code is contributed by aashish1995
</script>

Complejidad de tiempo: O(n) donde n es el número de Nodes en la lista enlazada dada.
Fuente: http://cslibrary.stanford.edu/105/LinkedListProblems.pdf
Consulte el artículo completo sobre la división alterna de una lista enlazada individual determinada | ¡ Establezca 1 para más detalles!