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.
Java
// Java program to delete every k-th
// Node of a singly linked list.
class GFG{
// Linked list Node
static class Node
{
int data;
Node next;
}
// To remove complete list (Needed
// for case when k is 1)
static Node freeList(Node node)
{
while (node != null)
{
Node next = node.next;
node = next;
}
return node;
}
// Deletes every k-th node and
// returns head of modified list.
static Node deleteKthNode(Node head,
int k)
{
// If linked list is empty
if (head == null)
return null;
if (k == 1)
{
head = freeList(head);
return null;
}
// Initialize ptr and prev before
// starting traversal.
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
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
static void displayList(Node head)
{
Node temp = head;
while (temp != null)
{
System.out.print(temp.data +
" ");
temp = temp.next;
}
}
// Utility function to create a
// new node.
static Node newNode(int x)
{
Node temp = new Node();
temp.data = x;
temp.next = null;
return temp;
}
// Driver Code
public static void main(String args[])
{
// Start with the empty list
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);
}
}
// This code is contributed by Arnab Kundu
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