Dada una lista enlazada y dos números enteros M y N. Recorra la lista enlazada de modo que retenga M Nodes y luego elimine los siguientes N Nodes, continúe igual hasta el final de la lista enlazada.
Nivel de dificultad: Novato
Ejemplos:
Input: M = 2, N = 2 Linked List: 1->2->3->4->5->6->7->8 Output: Linked List: 1->2->5->6 Input: M = 3, N = 2 Linked List: 1->2->3->4->5->6->7->8->9->10 Output: Linked List: 1->2->3->6->7->8 Input: M = 1, N = 1 Linked List: 1->2->3->4->5->6->7->8->9->10 Output: Linked List: 1->3->5->7->9
La parte principal del problema es mantener los enlaces adecuados entre los Nodes, asegurarse de que se manejen todos los casos de esquina. A continuación se muestra la implementación en C de la función skipMdeleteN() que omite M Nodes y elimina N Nodes hasta el final de la lista. Se supone que M no puede ser 0.
C++
// C++ program to delete N nodes
// after M nodes of a linked list
#include <bits/stdc++.h>
using namespace std;
// A linked list node
class Node
{
public:
int data;
Node *next;
};
/* Function to insert a node
at the beginning */
void push(Node ** head_ref,
int new_data)
{
// Allocate node
Node* new_node = new Node();
// Put in the data
new_node->data = new_data;
// Link the old list off the
// new node
new_node->next = (*head_ref);
// Move the head to point to
// the new node
(*head_ref) = new_node;
}
// Function to print linked list
void printList(Node *head)
{
Node *temp = head;
while (temp != NULL)
{
cout<<temp->data<<" ";
temp = temp->next;
}
cout<<endl;
}
// Function to skip M nodes and then
// delete N nodes of the linked list.
void skipMdeleteN(Node *head,
int M, int N)
{
Node *curr = head, *t;
int count;
// The main loop that traverses
// through the whole list
while (curr)
{
// Skip M nodes
for (count = 1; count < M &&
curr!= NULL; count++)
curr = curr->next;
// If we reached end of list,
// then return
if (curr == NULL)
return;
// Start from next node and delete
// N nodes
t = curr->next;
for (count = 1; count<=N &&
t!= NULL; count++)
{
Node *temp = t;
t = t->next;
free(temp);
}
// Link the previous list with
// remaining nodes
curr->next = t;
// Set current pointer for next
// iteration
curr = t;
}
}
// Driver code
int main()
{
/* Create following linked list
1->2->3->4->5->6->7->8->9->10 */
Node* head = NULL;
int M=2, N=3;
push(&head, 10);
push(&head, 9);
push(&head, 8);
push(&head, 7);
push(&head, 6);
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
cout << "M = " << M<< " N = " <<
N << "Given Linked list is :";
printList(head);
skipMdeleteN(head, M, N);
cout<<"Linked list after deletion is :";
printList(head);
return 0;
}
// This code is contributed by rathbhupendra
Producción:
M = 2, N = 3 Given Linked list is : 1 2 3 4 5 6 7 8 9 10 Linked list after deletion is : 1 2 6 7
Complejidad de tiempo:
O(n) donde n es el número de Nodes en la lista enlazada.
Espacio Auxiliar: O(1)
Consulte el artículo completo sobre Eliminar N Nodes después de M Nodes de una lista vinculada para obtener más detalles.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA