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.
Python3
# Python3 program to delete every # k-th Node of a singly linked list. import math # Linked list Node class Node: def __init__(self, data): self.data = data self.next = None # To remove complete list (Needed # for case when k is 1) def freeList(node): while (node != None): next = node.next node = next return node # Deletes every k-th node and # returns head of modified list. def deleteKthNode(head, k): # If linked list is empty if (head == None): return None if (k == 1): freeList(head) return None # Initialize ptr and prev before # starting traversal. ptr = head prev = None # Traverse list and delete every # k-th node count = 0 while (ptr != None): # Increment Node count count = count + 1 # 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 def displayList(head): temp = head while (temp != None): print(temp.data, end = ' ') temp = temp.next # Utility function to create # a new node. def newNode( x): temp = Node(x) temp.data = x temp.next = None return temp # Driver Code if __name__=='__main__': # Start with the empty list 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) k = 3 head = deleteKthNode(head, k) displayList(head) # This code is contributed by Srathore
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