Dada una lista enlazada, escribe una función para invertir cada k Node (donde k es una entrada a la función).
Ejemplos:
Inputs: 1->2->3->4->5->6->7->8->NULL and k = 3 Output: 3->2->1->6->5->4->8->7->NULL. Inputs: 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 enlazada 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 siguiente puntero del Node anterior al elemento superior de la pila. Repita este proceso, hasta llegar a NULL.
Este algoritmo usa O(k) espacio adicional.
Implementación:
C++
// C++ program to reverse a linked list in groups
// of given size
#include <bits/stdc++.h>
using namespace std;
/* Link list node */
struct Node {
int data;
struct Node* next;
};
/* Reverses the linked list in groups of size k
and returns the pointer to the new head node. */
struct Node* Reverse(struct Node* head, int k)
{
// Create a stack of Node*
stack<Node*> mystack;
struct Node* current = head;
struct 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.top();
head = prev;
mystack.pop();
} else {
prev->next = mystack.top();
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 */
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node =
(struct Node*)malloc(sizeof(struct 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;
}
/* Function to print linked list */
void printList(struct Node* node)
{
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
}
/* Driver program to test above function*/
int main(void)
{
/* Start with the empty list */
struct Node* head = NULL;
/* Created Linked list is 1->2->3->4->5->6->7->8->9 */
push(&head, 9);
push(&head, 8);
push(&head, 7);
push(&head, 6);
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
printf("\nGiven linked list \n");
printList(head);
head = Reverse(head, 3);
printf("\nReversed Linked list \n");
printList(head);
return 0;
}
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
Python3
# Python3 program to reverse a Linked List
# in groups of given size
# Node class
class Node(object):
__slots__ = 'data', 'next'
# Constructor to initialize the node object
def __init__(self, data = None, next = None):
self.data = data
self.next = next
def __repr__(self):
return repr(self.data)
class LinkedList(object):
# Function to initialize head
def __init__(self):
self.head = None
# Utility function to print nodes
# of LinkedList
def __repr__(self):
nodes = []
curr = self.head
while curr:
nodes.append(repr(curr))
curr = curr.next
return '[' + ', '.join(nodes) + ']'
# Function to insert a new node at
# the beginning
def prepend(self, data):
self.head = Node(data = data,
next = self.head)
# Reverses the linked list in groups of size k
# and returns the pointer to the new head node.
def reverse(self, k = 1):
if self.head is None:
return
curr = self.head
prev = None
new_stack = []
while curr is not None:
val = 0
# Terminate the loop whichever comes first
# either current == None or value >= k
while curr is not None and val < k:
new_stack.append(curr.data)
curr = curr.next
val += 1
# Now pop the elements of stack one by one
while new_stack:
# If final list has not been started yet.
if prev is None:
prev = Node(new_stack.pop())
self.head = prev
else:
prev.next = Node(new_stack.pop())
prev = prev.next
# Next of last element will point to None.
prev.next = None
return self.head
# Driver Code
llist = LinkedList()
llist.prepend(9)
llist.prepend(8)
llist.prepend(7)
llist.prepend(6)
llist.prepend(5)
llist.prepend(4)
llist.prepend(3)
llist.prepend(2)
llist.prepend(1)
print("Given linked list")
print(llist)
llist.head = llist.reverse(3)
print("Reversed Linked list")
print(llist)
# This code is contributed by
# Sagar Kumar Sinha(sagarsinha7777)
C#
// C# program to reverse a linked list
// in groups of given size
using System;
using System.Collections;
class GfG
{
/* Link list node */
public class Node
{
public int data;
public 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 mystack = new Stack();
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.Count > 0)
{
// If final list has not been started yet.
if (prev == null)
{
prev = (Node)mystack.Peek();
head = prev;
mystack.Pop();
}
else
{
prev.next = (Node)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)
{
Console.Write(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);
Console.WriteLine("Given linked list ");
printList(head);
head = Reverse(head, 3);
Console.WriteLine();
Console.WriteLine("Reversed Linked list ");
printList(head);
}
}
// This code is contributed by Arnab Kundu
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 Linked list 3 2 1 6 5 4 9 8 7
Complejidad del tiempo: O(N) , ya que estamos usando un bucle para atravesar N veces. Donde N es el número de Nodes en la lista enlazada.
Espacio auxiliar: O(k) , ya que estamos usando espacio adicional para la pila.
Este artículo es una contribución de Jatin Goyal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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