Eliminar el nodo medio de una lista enlazada en C ++

C ++ borrar asiento intermedio de la lista enlazada: Aquí, estamos implementando programa en C ++ para eliminar el nodo medio de una lista enlazada en C ++ .

Dada una sola lista enlazada y tenemos que eliminar el medio del elemento de la lista enlazada.

Si la longitud de la lista enlazada es impar a continuación, eliminar ((n + 1) / 2) ésimo término de la lista enlazada y si la lista es de longitud incluso entonces borrar el (n / 2 + 1) -ésimo término de la lista gustado.

Ejemplo 1:

    If we have a Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7
After deleting the middle node the linked list will be:
1 → 2 → 3 → 5 → 6 → 7
4 is the middle node

Ejemplo 2:

    If we have a Linked List : 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8
After deleting the middle node the linked list will be:
1 → 2 → 3 → 4 → 6 → 7 → 8
5 is the middle node

Algoritmo:

Para resolver el problema se sigue el siguiente procedimiento,

  1. Iniciamos los dos nodo nombre del puntero tan lento, rápido. (Como algo tortuga de Floyd, consulte el enlace a mi artículo de fusión especie en la lista enlazada).
  2. Cada vez que incrementamos el lento por uno mientras que el puntero de incremento rápido en dos.
  3. Repita el paso 2 hasta que el puntero rápido que pasa al final de la lista enlazada.
  4. Cuando el indicador rápido que pasa al final de la lista, al mismo tiempo lentas puntero apunta a la mitad de la lista enlazada.
  5. A continuación, elimine el nodo intermedio.

implementación en C ++:

#include <bits/stdc++.h>
using namespace std;
struct node{
int data;
node* next;
};
//Create a new node
struct node* create_node(int x){
struct node* temp= new node;
temp->data=x;
temp->next=NULL;
return temp;
}
//Enter the node into the linked list
void push(node** head,int x){
struct node* store=create_node(x);
if(*head==NULL){
*head =store;
return;
}
struct node* temp=*head;
while(temp->next){
temp=temp->next;
}
temp->next=store;
}
//Delete the middle node from the linked list
void delete_node(node** head){
if((*head)->next==NULL){
*head=NULL;
return;
}
struct node* fast=(*head)->next;
struct node* slow=*head;
while(fast && fast->next && fast->next->next){
slow=slow->next;
fast=fast->next->next;
}
slow->next=slow->next->next;
}
//Print the list
void print(node* head){
struct node* temp=head;
while(temp){
cout<<temp->data<<" ";
temp=temp->next;
}
}
int main()
{
struct node* l=NULL;
push(&l,1);
push(&l,2);
push(&l,3);
push(&l,4);
push(&l,5);
push(&l,6);
cout<<"Before the delete operation"<<endl;
print(l);
delete_node(&l);
cout<<"nAfter the delete operation"<<endl;
print(l);
return 0;
}

salida

Before the delete operation
1 2 3 4 5 6
After the delete operation
1 2 3 5 6


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *