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 <stdio.h>
#include <stdlib.h>
// A linked list node
struct Node
{
int data;
struct Node *next;
};
/* Function to insert a node at
the beginning */
void push(struct Node ** head_ref,
int new_data)
{
// Allocate node
struct Node* new_node =
(struct Node*) malloc(sizeof(struct 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(struct Node *head)
{
struct Node *temp = head;
while (temp != NULL)
{
printf("%d ", temp->data);
temp = temp->next;
}
printf("");
}
// Function to skip M nodes and then
// delete N nodes of the linked list.
void skipMdeleteN(struct Node *head,
int M, int N)
{
struct 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++)
{
struct 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 */
struct 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);
printf("M = %d, N = %d
Given Linked list is :",
M, N);
printList(head);
skipMdeleteN(head, M, N);
printf(
"Linked list after deletion is :");
printList(head);
return 0;
}
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