Programa C++ 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.  

// C++ implementation to insert node at the middle
// of the linked list
#include <bits/stdc++.h>
 
using namespace std;
 
// structure of a node
struct Node {
    int data;
    Node* next;
};
 
// function to create and return a node
Node* getNode(int data)
{
    // allocating space
    Node* newNode = (Node*)malloc(sizeof(Node));
 
    // inserting the required data
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}
 
// function to insert node at the middle
// of the linked list
void insertAtMid(Node** head_ref, int x)
{
    // if list is empty
    if (*head_ref == NULL)
        *head_ref = getNode(x);
    else {
 
        // get a new node
        Node* newNode = getNode(x);
 
        Node* ptr = *head_ref;
        int 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
        int count = ((len % 2) == 0) ? (len / 2) :
                                    (len + 1) / 2;
        ptr = *head_ref;
 
        // '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
void display(Node* head)
{
    while (head != NULL) {
        cout << head->data << " ";
        head = head->next;
    }
}
 
// Driver program to test above
int main()
{
    // Creating the list 1->2->4->5
    Node* head = NULL;
    head = getNode(1);
    head->next = getNode(2);
    head->next->next = getNode(4);
    head->next->next->next = getNode(5);
 
    cout << "Linked list before insertion: ";
    display(head);
 
    int x = 3;
    insertAtMid(&head, x);
 
    cout << "
Linked list after insertion: ";
    display(head);
 
    return 0;
}

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 espacial : O(1) ya que usa espacio constante

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. 

// C++ implementation to insert node at the middle
// of the linked list
#include <bits/stdc++.h>
 
using namespace std;
 
// structure of a node
struct Node {
    int data;
    Node* next;
};
 
// function to create and return a node
Node* getNode(int data)
{
    // allocating space
    Node* newNode = (Node*)malloc(sizeof(Node));
 
    // inserting the required data
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}
 
// function to insert node at the middle
// of the linked list
void insertAtMid(Node** head_ref, int x)
{
    // if list is empty
    if (*head_ref == NULL)
        *head_ref = getNode(x);
 
    else {
        // get a new node
        Node* newNode = getNode(x);
 
        // assign values to the slow and fast
        // pointers
        Node* slow = *head_ref;
        Node* fast = (*head_ref)->next;
 
        while (fast && fast->next) {
 
            // 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
void display(Node* head)
{
    while (head != NULL) {
        cout << head->data << " ";
        head = head->next;
    }
}
 
// Driver program to test above
int main()
{
    // Creating the list 1->2->4->5
    Node* head = NULL;
    head = getNode(1);
    head->next = getNode(2);
    head->next->next = getNode(4);
    head->next->next->next = getNode(5);
 
    cout << "Linked list before insertion: ";
    display(head);
 
    int x = 3;
    insertAtMid(&head, x);
 
    cout << "
Linked list after insertion: ";
    display(head);
 
    return 0;
}

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.