Dada una lista enlazada individualmente, su tarea es eliminar cada K-ésimo Node de la lista enlazada. Suponga que K siempre es menor o igual que la longitud de la lista enlazada.
Ejemplos:
Input: 1->2->3->4->5->6->7->8
k = 3
Output: 1->2->4->5->7->8
As 3 is the k-th node after its deletion list
would be 1->2->4->5->6->7->8
And now 4 is the starting node then from it, 6
would be the k-th node. So no other kth node
could be there.So, final list is:
1->2->4->5->7->8.
Input: 1->2->3->4->5->6
k = 1
Output: Empty list
All nodes need to be deleted
La idea es recorrer la lista desde el principio y realizar un seguimiento de los Nodes visitados después de la última eliminación. Cada vez que el conteo se convierte en k, elimine el Node actual y restablezca el conteo a 0.
Traverse list and do following
(a) Count node before deletion.
(b) If (count == k) that means current
node is to be deleted.
(i) Delete current node i.e. do
// assign address of next node of
// current node to the previous node
// of the current node.
prev->next = ptr->next i.e.
(ii) Reset count as 0, i.e., do count = 0.
(c) Update prev node if count != 0 and if
count is 0 that means that node is a
starting point.
(d) Update ptr and continue until all
k-th node gets deleted.
A continuación se muestra la implementación.
C++
// C++ program to delete every k-th
// Node of a singly linked list.
#include<bits/stdc++.h>
using namespace std;
// Linked list Node
struct Node
{
int data;
struct Node* next;
};
// To remove complete list (Needed
// for case when k is 1)
void freeList(Node *node)
{
while (node != NULL)
{
Node *next = node->next;
delete (node);
node = next;
}
}
// Deletes every k-th node and returns head
// of modified list.
Node *deleteKthNode(struct Node *head,
int k)
{
// If linked list is empty
if (head == NULL)
return NULL;
if (k == 1)
{
freeList(head);
return NULL;
}
// Initialize ptr and prev before
// starting traversal.
struct Node *ptr = head, *prev = NULL;
// Traverse list and delete every
// k-th node
int count = 0;
while (ptr != NULL)
{
// Increment Node count
count++;
// Check if count is equal to k
// if yes, then delete current Node
if (k == count)
{
// Put the next of current Node in
// the next of previous Node
delete(prev->next);
prev->next = ptr->next;
// Set count = 0 to reach further
// k-th Node
count = 0;
}
// Update prev if count is not 0
if (count != 0)
prev = ptr;
ptr = prev->next;
}
return head;
}
// Function to print linked list
void displayList(struct Node *head)
{
struct Node *temp = head;
while (temp != NULL)
{
cout << temp->data << " ";
temp = temp->next;
}
}
// Utility function to create
// a new node.
struct Node *newNode(int x)
{
Node *temp = new Node;
temp->data = x;
temp->next = NULL;
return temp;
}
// Driver code
int main()
{
// Start with the empty list
struct Node* head = newNode(1);
head->next = newNode(2);
head->next->next = newNode(3);
head->next->next->next = newNode(4);
head->next->next->next->next =
newNode(5);
head->next->next->next->next->next =
newNode(6);
head->next->next->next->next->next->next =
newNode(7);
head->next->next->next->next->next->next->next =
newNode(8);
int k = 3;
head = deleteKthNode(head, k);
displayList(head);
return 0;
}
Producción:
1 2 4 5 7 8
Complejidad de tiempo: O(n)
¡ Consulte el artículo completo sobre Eliminar cada k-ésimo Node de la 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