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.
Java
// Java program to reverse a linked list
// in groups of given size
import java.util.*;
class GfG
{
// Link list node
static class Node
{
int data;
Node next;
}
static Node head = null;
/* Reverses the linked list in groups
of size k and returns the pointer
to the new head node. */
static Node Reverse(Node head, int k)
{
// Create a stack of Node*
Stack<Node> mystack =
new Stack<Node> ();
Node current = head;
Node prev = null;
while (current != null)
{
// Terminate the loop whichever
// comes first either current == NULL
// or count >= k
int 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.size() > 0)
{
// If final list has not been
// started yet.
if (prev == null)
{
prev = mystack.peek();
head = prev;
mystack.pop();
}
else
{
prev.next = mystack.peek();
prev = prev.next;
mystack.pop();
}
}
}
// Next of last element will point
// to NULL.
prev.next = null;
return head;
}
// UTILITY FUNCTIONS
// Function to push a node
static void push( int new_data)
{
// Allocate node
Node 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
static void printList(Node node)
{
while (node != null)
{
System.out.print(node.data + " ");
node = node.next;
}
}
// Driver code
public static void main(String[] args)
{
// 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);
System.out.println(
"Given linked list ");
printList(head);
head = Reverse(head, 3);
System.out.println();
System.out.println(
"Reversed Linked list ");
printList(head);
}
}
// This code is contributed by Prerna Saini
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