Dada una lista enlazada, escribe una función para invertir cada k Node (donde k es una entrada a la función).
Ejemplos:
Input: 1->2->3->4->5->6->7->8->NULL and k = 3 Output: 3->2->1->6->5->4->8->7->NULL. Input: 1->2->3->4->5->6->7->8->NULL and k = 5 Output: 5->4->3->2->1->8->7->6->NULL.
Ya hemos discutido su solución en la publicación a continuación
Invertir una lista vinculada en grupos de tamaño dado | Conjunto 1
En esta publicación, hemos utilizado una pila que almacenará los Nodes de la lista vinculada dada. En primer lugar, inserte los k elementos de la lista enlazada en la pila. Ahora extraiga los elementos uno por uno y realice un seguimiento del Node previamente extraído. Apunte el puntero siguiente del Node anterior al elemento superior de la pila. Repita este proceso, hasta llegar a NULL.
Este algoritmo usa O(k) espacio adicional.
Javascript
<script>
// Javascript program to reverse a linked list
// in groups of given size
class GfG
{
// Link list node
class Node
{
constructor()
{
this.data = 0;
this.next = null;
}
}
var head = null;
/* Reverses the linked list in groups of
size k and returns the pointer to the new head node. */
function Reverse(head, k)
{
// Create a stack of Node*
var mystack = [];
var current = head;
var prev = null;
while (current != null)
{
// Terminate the loop whichever comes
// first either current == NULL or
// count >= k
var count = 0;
while (current != null && count < k)
{
mystack.push(current);
current = current.next;
count++;
}
// Now pop the elements of stack one
// by one
while (mystack.length > 0)
{
// If final list has not been
// started yet.
if (prev == null)
{
prev = mystack.pop();
head = prev;
}
else
{
prev.next = mystack.pop();
prev = prev.next;
}
}
}
// Next of last element will point
// to NULL.
prev.next = null;
return head;
}
// UTILITY FUNCTIONS
// Function to push a node
function push(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;
// Move the head to point to the
// new node
head = new_node;
}
// Function to print linked list
function printList(node)
{
while (node != null)
{
document.write(node.data + " ");
node = node.next;
}
}
}
// Driver code
// Start with the empty list
// Node head = null;
/* Created Linked list is
1->2->3-> 4->5->6->7->8->9 */
push(9);
push(8);
push(7);
push(6);
push(5);
push(4);
push(3);
push(2);
push(1);
document.write("Given linked list <br/>");
printList(head);
head = Reverse(head, 3);
document.write("<br/>");
document.write("Reversed Linked list <br/>");
printList(head);
// This code contributed by aashish1995
</script>
Producción:
Given Linked List 1 2 3 4 5 6 7 8 9 Reversed list 3 2 1 6 5 4 9 8 7
Consulte el artículo completo sobre Invertir una lista vinculada en grupos de tamaño determinado | Set 2 para 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