Invertir una lista enlazada en grupos de tamaño dado usando el programa C ++

En este artículo, vamos a aprender cómo revertir una lista gustado en grupos de tamaño dado? Este artículo contiene planteamiento del problema, la explicación, algoritmo, C ++ aplicación y la salida.

Dada una lista enlazada de tamaño N . La tarea es revertir todos los k nodos en la lista enlazada.

Explicación y ejemplo:

    If a linked listis: 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 
The value of k is 2
Then the linked list looks like: 2 → 1 → 4 → 3 → 6 → 5 → 8 → 7

Algoritmo:

Para resolver el problema se sigue este algoritmo,

Hay una función llamada como inversa (start_node, k) y reveses la k nodos de la start_node y cada vez que devuelve un nodo de inicio de ese grupo.

  1. Almacenamos el siguiente puntero en la variable de nodo y conectamos el puntero actual a la cabeza de otro nombre de variable de nodo como prev .
  2. En el nodo de la lista cabeza reverso de la LinkedList llegará a la cola y que conecte el siguiente nodo al siguiente puntero del cabeza .

    head->next=Reverse(start->node,k)
Reverse function:
//base case
if(head==NULL){
return NULL;
}
//declarations
struct node* next=NULL;
struct node* prev=NULL;
struct node* curr=head;
int count=0;
while(curr&& count<k){
//we store the next pointer into next
//and connect the current pointer to the head of the prev
next=curr->next;
curr->next=prev;
prev=curr;
curr=next;
count++;
}
//in the reverse list head node of the linked list will come to the tail
//for this we connect the next node to it's next pointer
head->next=reverse(curr,k);
return prev;

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;
}
//Reverse the linked list
struct node* reverse(node* head, int k){
if(head==NULL){
return NULL;
}
struct node* next=NULL;
struct node* prev=NULL;
struct node* curr=head;
int count=0;
while(curr && count<k){
//we store the next pointer into next
//and connect the current pointer to the head of the prev
next=curr->next;
curr->next=prev;
prev=curr;
curr=next;
count++;
}
//in the reverse list head node of the linkedlist will come to the tail
//for this we connect the next node to it's next pointer
head->next=reverse(curr,k);
return prev;
}
//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 reverse operation"<<endl;
print(l);
l=reverse(l,2);
cout<<"nAfter the reverse operation"<<endl;
print(l);
return 0;
}

salida

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


Deja un comentario

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