Invertir una única lista enlazada

En este artículo, vamos a ver cómo revertir una sola lista enlazada ? Este problema ha llegado a ronda de Amazon, Microsoft codificación.

Planteamiento del problema: Dada una lista enlazada revertirla sin utilizar ningún espacio adicional (en O (1) espacio de complejidad).

Solución:

de marcha atrás una única lista enlazada se trata de invertir la dirección de enlace. Podemos resolver el problema anterior con los siguientes pasos:

1. La construcción de la lista enlazada

En primer lugar, construimos la lista enlazada mediante la inserción de cada nodo al principio. Para un análisis detallado de cómo construir una lista enlazada mediante la inserción al inicio, la amabilidad de ir a través de este artículo completo: lista simplemente enlazada inserción

2. Función de revertir la lista de enlaces

Como se dijo anteriormente, la básica idea de revertir una lista enlazada es para invertir el sentido de la vinculación. Este concepto se puede implementar sin necesidad de utilizar ningún espacio adicional. Necesitamos tres punteros * prev , * cur , * próxima para implementar la función. Estas variables se denominan en consecuencia para indicar su parte que sirve en la función.

* prev – para almacenar el nodo anterior que se convertirá en última instancia, el siguiente nodo después de la inversión para el nodo actual

* act – para almacenar el nodo actual

* próxima – para almacenar la siguiente nodo que se convertirá en nodo actual en la siguiente iteración.

Inicializar * prev y * junto a NULL, * act a la cabeza

while(cur!=NULL)
Set *nextto cur->next
Set cur->nextto *prev
Set *prev to *cur
Set *cur to *next
End While loop
Set head to *prev

3. Imprimir la lista Invertida ligado

Ejemplo:

Let the linked list be 1->2->3->4->5->NULL
(for simplicity in understanding representing
pointer to node by node value)
Head is 1
Initialize:
cur =1, prev=NULL, next=NULL
in iteration 1:
next=2
cur->next=NULL
prev=1
cur=2
thus reversed part: 1->NULL
in iteration 2:
next=3
cur->next=1
prev=2
cur=3
thus reversed part: 2->1->NULL
in iteration 3:
next=4
cur->next=2
prev=3
cur=4
thus reversed part: 3->2->1->NULL
in iteration 4:
next=5
cur->next=3
prev=4
cur=5
thus reversed part: 4->3->2->1->NULL
in iteration 5:
next=NULL
cur->next=4
prev=5
cur=NULL
thus reversed part: 5->4->3->2->1->NULL
iteration ends at cur is NULL
linked list reversed, head at 5

programa en C ++ para revertir una única lista enlazada

#include<bits/stdc++.h>
using namespace std;
class node{
public:
int data; // data field
node *next;
};
node* reverse(node* head){
node *next=NULL,*cur=head,*prev=NULL; //initialize the pointers
while(cur!=NULL){//loop till the end of linked list
next=cur->next;//next = cur->next to store the rest of the list;
cur->next=prev;//change the direction of linked list
prev=cur; //update prev
cur=next; //update cur
}
head=prev; //update head
return head; //return head
}
void traverse(node* head){
node* current=head; // current node set to head
int count=0; // to count total no of nodes
printf("ntraversing the listn");
while(current!=NULL){ //traverse until current node isn't NULL
count++; //increase node count
printf("%d ",current->data);
current=current->next; // go to next node
}
printf("ntotal no of nodes : %dn",count);
}
node* creatnode(int d){
node* temp=(node*)malloc(sizeof(node));
temp->data=d;
temp->next=NULL;
return temp;
}
int main(){
printf("creating the linked list by inserting new nodes at the beginingn");
printf("enter 0 to stop building the list, else enter any integern");
int k,count=1,x;
node* curr;
scanf("%d",&k);
node* head=creatnode(k); //buliding list, first node
scanf("%d",&k);
//inserting at begining////
while(k){
curr=creatnode(k);
curr->next=head; //inserting each new node at the begining
head=curr;
scanf("%d",&k);
}
traverse(head); // displaying the list
cout<<"reversing the list............"<<endl;
head=reverse(head);// reverse the linked list
traverse(head);//display reversed linked list
return 0;
}

salida

creating the linked list by inserting new nodes at the begining 
enter 0 to stop building the list, else enter any integer
6
7
8
9
4
3
3
1
0
traversing the list
1 3 3 4 9 8 7 6
total no of nodes : 8
reversing the list............
traversing the list
6 7 8 9 4 3 3 1
total no of nodes : 8


Deja un comentario

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