Programa Java para la división alterna de un conjunto de listas 1 con enlaces individuales dados

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.

// Java program to implement
// the above approach
static void AlternatingSplit(Node source, 
                             Node aRef, 
                             Node bRef) 
{
    Node aDummy = new Node();
      
    // Points to the last node in 'a' 
    Node aTail = aDummy; 
    Node bDummy = new Node();
  
    // Points to the last node in 'b' 
    Node bTail = bDummy; 
    Node 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 rutvik_56

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!