Elimine cada k-ésimo Node de una lista enlazada circular hasta que solo quede un Node. Además, imprima las listas intermedias.
Ejemplos:
Input : n=4, k=2, list = 1->2->3->4 Output : 1->2->3->4->1 1->2->4->1 2->4->2 2->2 Input : n=9, k=4, list = 1->2->3->4->5->6->7->8->9 Output : 1->2->3->4->5->6->7->8->9->1 1->2->3->4->6->7->8->9->1 1->2->3->4->6->7->8->1 1->2->3->6->7->8->1 2->3->6->7->8->2 2->3->6->8->2 2->3->8->2 2->3->2 2->2
Algoritmo
Repita los siguientes pasos hasta que solo quede un Node en la lista.
Caso 1 : La lista está vacía.
Si la lista está vacía, simplemente devuélvela.
Caso 2 : La lista tiene un solo Node.
Si a la lista solo le queda un Node, imprimiremos la lista y la devolveremos cuando alcancemos nuestro objetivo.
Caso 3 : La lista tiene más de un Node.
Defina dos punteros curr y prev e inicialice el puntero curr con el Node principal.
Recorra la lista usando el puntero actual iterándolo k veces.
- El Node a eliminar es el primer Node de la lista.
Condiciones para verificar esto ( curr == head && curr->next == head).
En caso afirmativo, mueva anterior hasta que llegue al último Node. Después de que prev llegue al último Node, configure head = head -> next y prev -> next = head. Eliminar actual - El Node a eliminar es el último Node de la lista.
La condición para verificar esto es (curr -> next == head).
Si curr es el último Node. Establezca prev -> next = head y elimine el Node curr gratis (curr). - El que se eliminará no es ni el primer Node ni el último Node, luego establezca anterior -> siguiente = temporal -> siguiente y elimine curr.
C++
// C++ program to delete every kth Node from
// circular linked list.
#include <bits/stdc++.h>
using namespace std;
/* structure for a Node */
struct Node {
int data;
Node* next;
Node(int x)
{
data = x;
next = NULL;
}
};
/*Utility function to print the circular linked list*/
void printList(Node* head)
{
if (head == NULL)
return;
Node* temp = head;
do {
cout << temp->data << "->";
temp = temp->next;
} while (temp != head);
cout << head->data << endl;
}
/*Function to delete every kth Node*/
void deleteK(Node** head_ref, int k)
{
Node* head = *head_ref;
// If list is empty, simply return.
if (head == NULL)
return;
// take two pointers - current and previous
Node *curr = head, *prev;
while (true) {
// Check if Node is the only Node\
// If yes, we reached the goal, therefore
// return.
if (curr->next == head && curr == head)
break;
// Print intermediate list.
printList(head);
// If more than one Node present in the list,
// Make previous pointer point to current
// Iterate current pointer k times,
// i.e. current Node is to be deleted.
for (int i = 0; i < k; i++) {
prev = curr;
curr = curr->next;
}
// If Node to be deleted is head
if (curr == head) {
prev = head;
while (prev->next != head)
prev = prev->next;
head = curr->next;
prev->next = head;
*head_ref = head;
free(curr);
}
// If Node to be deleted is last Node.
else if (curr->next == head) {
prev->next = head;
free(curr);
}
else {
prev->next = curr->next;
free(curr);
}
}
}
/* Function to insert a Node at the end of
a Circular linked list */
void insertNode(Node** head_ref, int x)
{
// Create a new Node
Node* head = *head_ref;
Node* temp = new Node(x);
// if the list is empty, make the new Node head
// Also, it will point to itself.
if (head == NULL) {
temp->next = temp;
*head_ref = temp;
}
// traverse the list to reach the last Node
// and insert the Node
else {
Node* temp1 = head;
while (temp1->next != head)
temp1 = temp1->next;
temp1->next = temp;
temp->next = head;
}
}
/* Driver program to test above functions */
int main()
{
// insert Nodes in the circular linked list
struct Node* head = NULL;
insertNode(&head, 1);
insertNode(&head, 2);
insertNode(&head, 3);
insertNode(&head, 4);
insertNode(&head, 5);
insertNode(&head, 6);
insertNode(&head, 7);
insertNode(&head, 8);
insertNode(&head, 9);
int k = 4;
// Delete every kth Node from the
// circular linked list.
deleteK(&head, k);
return 0;
}
Java
// Java program to delete every kth Node from
// circular linked list.
class GFG
{
/* structure for a Node */
static class Node
{
int data;
Node next;
Node(int x)
{
data = x;
next = null;
}
};
/*Utility function to print
the circular linked list*/
static void printList(Node head)
{
if (head == null)
return;
Node temp = head;
do
{
System.out.print( temp.data + "->");
temp = temp.next;
}
while (temp != head);
System.out.println(head.data );
}
/*Function to delete every kth Node*/
static Node deleteK(Node head_ref, int k)
{
Node head = head_ref;
// If list is empty, simply return.
if (head == null)
return null;
// take two pointers - current and previous
Node curr = head, prev=null;
while (true)
{
// Check if Node is the only Node\
// If yes, we reached the goal, therefore
// return.
if (curr.next == head && curr == head)
break;
// Print intermediate list.
printList(head);
// If more than one Node present in the list,
// Make previous pointer point to current
// Iterate current pointer k times,
// i.e. current Node is to be deleted.
for (int i = 0; i < k; i++)
{
prev = curr;
curr = curr.next;
}
// If Node to be deleted is head
if (curr == head)
{
prev = head;
while (prev.next != head)
prev = prev.next;
head = curr.next;
prev.next = head;
head_ref = head;
}
// If Node to be deleted is last Node.
else if (curr.next == head)
{
prev.next = head;
}
else
{
prev.next = curr.next;
}
}
return head;
}
/* Function to insert a Node at the end of
a Circular linked list */
static Node insertNode(Node head_ref, int x)
{
// Create a new Node
Node head = head_ref;
Node temp = new Node(x);
// if the list is empty, make the new Node head
// Also, it will point to itself.
if (head == null)
{
temp.next = temp;
head_ref = temp;
return head_ref;
}
// traverse the list to reach the last Node
// and insert the Node
else
{
Node temp1 = head;
while (temp1.next != head)
temp1 = temp1.next;
temp1.next = temp;
temp.next = head;
}
return head;
}
/* Driver code */
public static void main(String args[])
{
// insert Nodes in the circular linked list
Node head = null;
head = insertNode(head, 1);
head = insertNode(head, 2);
head = insertNode(head, 3);
head = insertNode(head, 4);
head = insertNode(head, 5);
head = insertNode(head, 6);
head = insertNode(head, 7);
head = insertNode(head, 8);
head = insertNode(head, 9);
int k = 4;
// Delete every kth Node from the
// circular linked list.
head = deleteK(head, k);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to delete every kth Node from # circular linked list. import math # structure for a Node class Node: def __init__(self, data): self.data = data self.next = None # Utility function to print the circular linked list def printList(head): if (head == None): return temp = head print(temp.data, end = "->") temp = temp.next while (temp != head): print(temp.data, end = "->") temp = temp.next print(head.data) # Function to delete every kth Node def deleteK(head_ref, k): head = head_ref # If list is empty, simply return. if (head == None): return # take two pointers - current and previous curr = head prev = None while True: # Check if Node is the only Node\ # If yes, we reached the goal, therefore # return. if (curr.next == head and curr == head): break # Print intermediate list. printList(head) # If more than one Node present in the list, # Make previous pointer point to current # Iterate current pointer k times, # i.e. current Node is to be deleted. for i in range(k): prev = curr curr = curr.next # If Node to be deleted is head if (curr == head): prev = head while (prev.next != head): prev = prev.next head = curr.next prev.next = head head_ref = head # If Node to be deleted is last Node. elif (curr.next == head) : prev.next = head else : prev.next = curr.next # Function to insert a Node at the end of #a Circular linked list def insertNode(head_ref, x): # Create a new Node head = head_ref temp = Node(x) # if the list is empty, make the new Node head # Also, it will po to itself. if (head == None): temp.next = temp head_ref = temp return head_ref # traverse the list to reach the last Node # and insert the Node else : temp1 = head while (temp1.next != head): temp1 = temp1.next temp1.next = temp temp.next = head return head # Driver Code if __name__=='__main__': # insert Nodes in the circular linked list head = None head = insertNode(head, 1) head = insertNode(head, 2) head = insertNode(head, 3) head = insertNode(head, 4) head = insertNode(head, 5) head = insertNode(head, 6) head = insertNode(head, 7) head = insertNode(head, 8) head = insertNode(head, 9) k = 4 # Delete every kth Node from the # circular linked list. deleteK(head, k) # This code is contributed by Srathore
C#
// C# program to delete every kth Node from
// circular linked list.
using System;
class GFG
{
/* structure for a Node */
public class Node
{
public int data;
public Node next;
public Node(int x)
{
data = x;
next = null;
}
};
/*Utility function to print
the circular linked list*/
static void printList(Node head)
{
if (head == null)
return;
Node temp = head;
do
{
Console.Write( temp.data + "->");
temp = temp.next;
}
while (temp != head);
Console.WriteLine(head.data );
}
/*Function to delete every kth Node*/
static Node deleteK(Node head_ref, int k)
{
Node head = head_ref;
// If list is empty, simply return.
if (head == null)
return null;
// take two pointers - current and previous
Node curr = head, prev = null;
while (true)
{
// Check if Node is the only Node\
// If yes, we reached the goal, therefore
// return.
if (curr.next == head && curr == head)
break;
// Print intermediate list.
printList(head);
// If more than one Node present in the list,
// Make previous pointer point to current
// Iterate current pointer k times,
// i.e. current Node is to be deleted.
for (int i = 0; i < k; i++)
{
prev = curr;
curr = curr.next;
}
// If Node to be deleted is head
if (curr == head)
{
prev = head;
while (prev.next != head)
prev = prev.next;
head = curr.next;
prev.next = head;
head_ref = head;
}
// If Node to be deleted is last Node.
else if (curr.next == head)
{
prev.next = head;
}
else
{
prev.next = curr.next;
}
}
return head;
}
/* Function to insert a Node at the end of
a Circular linked list */
static Node insertNode(Node head_ref, int x)
{
// Create a new Node
Node head = head_ref;
Node temp = new Node(x);
// if the list is empty, make the new Node head
// Also, it will point to itself.
if (head == null)
{
temp.next = temp;
head_ref = temp;
return head_ref;
}
// traverse the list to reach the last Node
// and insert the Node
else
{
Node temp1 = head;
while (temp1.next != head)
temp1 = temp1.next;
temp1.next = temp;
temp.next = head;
}
return head;
}
/* Driver code */
public static void Main(String []args)
{
// insert Nodes in the circular linked list
Node head = null;
head = insertNode(head, 1);
head = insertNode(head, 2);
head = insertNode(head, 3);
head = insertNode(head, 4);
head = insertNode(head, 5);
head = insertNode(head, 6);
head = insertNode(head, 7);
head = insertNode(head, 8);
head = insertNode(head, 9);
int k = 4;
// Delete every kth Node from the
// circular linked list.
head = deleteK(head, k);
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// javascript program to delete every kth Node from
// circular linked list. /* structure for a Node */
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
/*
* Utility function to print the circular linked list
*/
function printList(head) {
if (head == null)
return;
var temp = head;
do {
document.write(temp.data + "->");
temp = temp.next;
} while (temp != head);
document.write(head.data+"<br/>");
}
/* Function to delete every kth Node */
function deleteK(head_ref , k) {
var head = head_ref;
// If list is empty, simply return.
if (head == null)
return null;
// take two pointers - current and previous
var curr = head, prev = null;
while (true) {
// Check if Node is the only Node\
// If yes, we reached the goal, therefore
// return.
if (curr.next == head && curr == head)
break;
// Print intermediate list.
printList(head);
// If more than one Node present in the list,
// Make previous pointer point to current
// Iterate current pointer k times,
// i.e. current Node is to be deleted.
for (i = 0; i < k; i++) {
prev = curr;
curr = curr.next;
}
// If Node to be deleted is head
if (curr == head) {
prev = head;
while (prev.next != head)
prev = prev.next;
head = curr.next;
prev.next = head;
head_ref = head;
}
// If Node to be deleted is last Node.
else if (curr.next == head) {
prev.next = head;
} else {
prev.next = curr.next;
}
}
return head;
}
/*
* Function to insert a Node at the end of a Circular linked list
*/
function insertNode(head_ref , x) {
// Create a new Node
var head = head_ref;
var temp = new Node(x);
// if the list is empty, make the new Node head
// Also, it will point to itself.
if (head == null) {
temp.next = temp;
head_ref = temp;
return head_ref;
}
// traverse the list to reach the last Node
// and insert the Node
else {
var temp1 = head;
while (temp1.next != head)
temp1 = temp1.next;
temp1.next = temp;
temp.next = head;
}
return head;
}
/* Driver code */
// insert Nodes in the circular linked list
var head = null;
head = insertNode(head, 1);
head = insertNode(head, 2);
head = insertNode(head, 3);
head = insertNode(head, 4);
head = insertNode(head, 5);
head = insertNode(head, 6);
head = insertNode(head, 7);
head = insertNode(head, 8);
head = insertNode(head, 9);
var k = 4;
// Delete every kth Node from the
// circular linked list.
head = deleteK(head, k);
// This code is contributed by todaysgaurav
</script>
Producción:
1->2->3->4->5->6->7->8->9->1 1->2->3->4->6->7->8->9->1 1->2->3->4->6->7->8->1 1->2->3->6->7->8->1 2->3->6->7->8->2 2->3->6->8->2 2->3->8->2 2->3->2 2->2
Complejidad de tiempo: O (n * n), ya que estamos usando bucles anidados para atravesar n * n veces. para borrar e imprimir la lista enlazada. Donde n es el número de Nodes en la lista enlazada.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.