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:
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 program to test count function*/
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;
}
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
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
C#
// C# program to delete every k-th Node
// of a singly linked list.
using System;
class GFG
{
/* Linked list Node */
public class Node
{
public int data;
public 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)
{
Console.Write(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 PrinciRaj1992
Javascript
<script>
// Javascript program to delete every k-th Node
// of a singly linked list.
/* Linked list Node */
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
// To remove complete list (Needed for
// case when k is 1)
function freeList( node) {
while (node != null) {
next = node.next;
node = next;
}
return node;
}
// Deletes every k-th node and
// returns head of modified list.
function deleteKthNode( head , 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.
var ptr = head, prev = null;
// Traverse list and delete
// every k-th node
var 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 */
function displayList( head) {
temp = head;
while (temp != null) {
document.write(temp.data + " ");
temp = temp.next;
}
}
// Utility function to create a new node.
function newNode(x) {
temp = new Node();
temp.data = x;
temp.next = null;
return temp;
}
// Driver Code
/* 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);
var k = 3;
head = deleteKthNode(head, k);
displayList(head);
// This code contributed by umadevi9616
</script>
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