Programa Javascript para insertar un Node en medio de la lista enlazada

Dada una lista enlazada que contiene n Nodes. El problema es insertar un nuevo Node con datos x en el medio de la lista. Si n es par, entonces inserte el nuevo Node después del (n/2) enésimo Node, de lo contrario, inserte el nuevo Node después del (n+1)/2 enésimo Node.

Ejemplos: 

Input : list: 1->2->4->5
        x = 3
Output : 1->2->3->4->5

Input : list: 5->10->4->32->16
        x = 41
Output : 5->10->4->41->32->16

Método 1 (Usando la longitud de la lista enlazada): 
Encuentre la cantidad de Nodes o la longitud del enlace usando un recorrido. Que sea len . Calcule c = (len/2), si len es par, de lo contrario, c = (len+1)/2, si len es impar. Atraviese de nuevo los primeros c Nodes e inserte el nuevo Node después del c -ésimo Node.  

<script>
 
// Javascript implementation to insert node
// at the middle of the linked list
 
 
    var head; // head of list
 
    /* Node Class */
     class Node {
 
        // Constructor to create a new node
        constructor(d) {
            this.data = d;
            this.next = null;
        }
    }
 
    // function to insert node at the
    // middle of the linked list
    function insertAtMid(x) {
        // if list is empty
        if (head == null)
            head = new Node(x);
        else {
            // get a new node
            var newNode = new Node(x);
 
            var ptr = head;
            var len = 0;
 
            // calculate length of the linked list
            // , i.e, the number of nodes
            while (ptr != null) {
                len++;
                ptr = ptr.next;
            }
 
            // 'count' the number of nodes after which
            // the new node is to be inserted
            var count = ((len % 2) == 0) ? (len / 2) :
            (len + 1) / 2;
            ptr = head;
 
            // 'ptr' points to the node after which
            // the new node is to be inserted
            while (count-- > 1)
                ptr = ptr.next;
 
            // insert the 'newNode' and adjust
            // the required links
            newNode.next = ptr.next;
            ptr.next = newNode;
        }
    }
 
    // function to display the linked list
    function display() {
        var temp = head;
        while (temp != null) {
            document.write(temp.data + " ");
            temp = temp.next;
        }
    }
 
    // Driver program to test above
     
        // Creating the list 1.2.4.5
         
        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(4);
        head.next.next.next = new Node(5);
 
        document.write("Linked list before "
        + "insertion: ");
        display();
 
        var x = 3;
        insertAtMid(x);
 
        document.write("<br/>Linked list after" +
        " insertion: ");
        display();
 
// This code contributed by Rajput-Ji
 
</script>

Producción: 

Linked list before insertion: 1 2 4 5
Linked list after insertion: 1 2 3 4 5

Tiempo Complejidad : O(n)
Espacio Auxiliar : O(1)

Método 2 (usando dos punteros): 
basado en el algoritmo de Turtle y liebre que usa dos punteros, uno conocido como lento y el otro conocido como rápido . Este algoritmo ayuda a encontrar el Node medio de la lista enlazada. Se explica en el procedimiento de división frontal y negro de esta publicación. Ahora, puede insertar el nuevo Node después del Node medio obtenido del proceso anterior. Este enfoque requiere solo un único recorrido de la lista. 

<script>
 
// Javascript implementation to insert node
// at the middle of the linked list
 
var head; // head of list
 
    /* Node Class */
     class Node {
 
// Constructor to create a new node
constructor(val) {
    this.data = val;
    this.next = null;
}
}
 
    // function to insert node at the
    // middle of the linked list
    function insertAtMid(x) {
        // if list is empty
        if (head == null)
            head = new Node(x);
 
        else {
            // get a new node
    var newNode = new Node(x);
 
            // assign values to the slow
            // and fast pointers
    var slow = head;
    var fast = head.next;
 
            while (fast != null && fast.next != null)
            {
                // move slow pointer to next node
                slow = slow.next;
 
                // move fast pointer two nodes
                // at a time
                fast = fast.next.next;
            }
 
            // insert the 'newNode' and adjust
            // the required links
            newNode.next = slow.next;
            slow.next = newNode;
        }
    }
 
    // function to display the linked list
      function display() {
       var temp = head;
        while (temp != null) {
            document.write(temp.data + " ");
            temp = temp.next;
        }
    }
 
    // Driver program to test above
     
        // Creating the list 1.2.4.5
        head = null;
        head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(4);
        head.next.next.next = new Node(5);
 
        document.write(
        "Linked list before" + " insertion: "
        );
        display();
 
        var x = 3;
        insertAtMid(x);
 
        document.write(
        "<br/>Linked list after" + " insertion: "
        );
        display();
 
// This code is contributed by todaysgaurav
 
</script>

Producción: 

Linked list before insertion: 1 2 4 5
Linked list after insertion: 1 2 3 4 5

Complejidad de tiempo: O(n)

Complejidad del espacio : O(n) donde n es el tamaño de la lista enlazada

Consulte el artículo completo sobre Insertar Node en el medio de la lista vinculada para obtener más detalles.