Dada una lista enlazada y dos números enteros M y N. Recorra la lista enlazada de modo que retenga M Nodes y luego elimine los siguientes N Nodes, continúe igual hasta el final de la lista enlazada.
Nivel de dificultad: Novato
Ejemplos:
Input: M = 2, N = 2 Linked List: 1->2->3->4->5->6->7->8 Output: Linked List: 1->2->5->6 Input: M = 3, N = 2 Linked List: 1->2->3->4->5->6->7->8->9->10 Output: Linked List: 1->2->3->6->7->8 Input: M = 1, N = 1 Linked List: 1->2->3->4->5->6->7->8->9->10 Output: Linked List: 1->3->5->7->9
La parte principal del problema es mantener los enlaces adecuados entre los Nodes, asegurarse de que se manejen todos los casos de esquina. A continuación se muestra la implementación en C de la función skipMdeleteN() que omite M Nodes y elimina N Nodes hasta el final de la lista. Se supone que M no puede ser 0.
Javascript
<script>
// Javascript program to delete N nodes
// after M nodes of a linked list
// A linked list node
class Node
{
constructor()
{
this.data = 0;
this.next = null;
}
}
// Function to insert a node at
// the beginning
function push(head_ref, new_data)
{
// Allocate node
var new_node = new Node();
// Put in the data
new_node.data = new_data;
// Link the old list off the
// new node
new_node.next = (head_ref);
// Move the head to point to
// the new node
(head_ref) = new_node;
return head_ref;
}
// Function to print linked list
function printList(head)
{
var temp = head;
while (temp != null)
{
document.write(temp.data + " ");
temp = temp.next;
}
document.write("<br/>");
}
// Function to skip M nodes and then
// delete N nodes of the linked list.
function skipMdeleteN(head, M , N)
{
var curr = head, t;
var count;
// The main loop that traverses
// through the whole list
while (curr != null)
{
// Skip M nodes
for (count = 1; count < M &&
curr != null; count++)
curr = curr.next;
// If we reached end of list,
// then return
if (curr == null)
return;
// Start from next node and delete
// N nodes
t = curr.next;
for (count = 1; count <= N &&
t != null; count++)
{
var temp = t;
t.next;
}
// Link the previous list with
// remaining nodes
curr.next = t;
// Set current pointer for next
// iteration
curr = t;
}
}
// Driver code
/* Create following linked list
1.2.3.4.5.6.7.8.9.10 */
var head = null;
var M = 2, N = 3;
head = push(head, 10);
head = push(head, 9);
head = push(head, 8);
head = push(head, 7);
head = push(head, 6);
head = push(head, 5);
head = push(head, 4);
head = push(head, 3);
head = push(head, 2);
head = push(head, 1);
document.write(
"M = "+M+", N = " + N +
"<br/>Given Linked list is :<br/>");
printList(head);
skipMdeleteN(head, M, N);
document.write(
"<br/>Linked list after deletion is :<br/>");
printList(head);
// This code is contributed by gauravrajput1
</script>
Producción:
M = 2, N = 3 Given Linked list is : 1 2 3 4 5 6 7 8 9 10 Linked list after deletion is : 1 2 6 7
Complejidad de tiempo:
O(n) donde n es el número de Nodes en la lista enlazada.
Espacio Auxiliar : O(1)
Consulte el artículo completo sobre Eliminar N Nodes después de M Nodes de una 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