Dada una lista enlazada, escribe una función para invertir cada k Node (donde k es una entrada a la función).
Ejemplo:
Entrada : 1->2->3->4->5->6->7->8->NULL, K = 3
Salida : 3->2->1->6->5->4- >8->7->NULO
Entrada : 1->2->3->4->5->6->7->8->NULO, K = 5
Salida : 5->4->3-> 2->1->8->7->6->NULO
Algoritmo : inverso (cabeza, k)
- Invierta la primera sublista de tamaño k. Mientras retrocede, realice un seguimiento del siguiente Node y del Node anterior. Deje que el puntero al siguiente Node sea next y el puntero al Node anterior sea prev . Consulte esta publicación para invertir una lista vinculada.
- head->next = reverse(next, k) (Llama recursivamente al resto de la lista y vincula las dos sublistas)
- Return prev ( prev se convierte en el nuevo encabezado de la lista (ver los diagramas de un método iterativo de esta publicación )
La siguiente imagen muestra cómo funciona la función inversa:
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to reverse a linked list
// in groups of given size
#include <bits/stdc++.h>
using namespace std;
/* Link list node */
class Node {
public:
int data;
Node* next;
};
/* Reverses the linked list in groups
of size k and returns the pointer
to the new head node. */
Node* reverse(Node* head, int k)
{
// base case
if (!head)
return NULL;
Node* current = head;
Node* next = NULL;
Node* prev = NULL;
int count = 0;
/*reverse first k nodes of the linked list */
while (current != NULL && count < k) {
next = current->next;
current->next = prev;
prev = current;
current = next;
count++;
}
/* next is now a pointer to (k+1)th node
Recursively call for the list starting from current.
And make rest of the list as next of first node */
if (next != NULL)
head->next = reverse(next, k);
/* prev is new head of the input list */
return prev;
}
/* UTILITY FUNCTIONS */
/* Function to push a node */
void push(Node** head_ref, 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_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Function to print linked list */
void printList(Node* node)
{
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
}
/* Driver code*/
int main()
{
/* Start with the empty list */
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);
cout << "Given linked list \n";
printList(head);
head = reverse(head, 3);
cout << "\nReversed Linked list \n";
printList(head);
return (0);
}
// This code is contributed by rathbhupendra
C
// C program to reverse a linked list in groups of given size
#include<stdio.h>
#include<stdlib.h>
/* 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)
{
if (!head)
return NULL;
struct Node* current = head;
struct Node* next = NULL;
struct Node* prev = NULL;
int count = 0;
/*reverse first k nodes of the linked list */
while (current != NULL && count < k)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
count++;
}
/* next is now a pointer to (k+1)th node
Recursively call for the list starting from current.
And make rest of the list as next of first node */
if (next != NULL)
head->next = reverse(next, k);
/* prev is new head of the input list */
return prev;
}
/* 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 code*/
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
class LinkedList {
Node head; // head of list
/* Linked list Node*/
class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
Node reverse(Node head, int k)
{
if(head == null)
return null;
Node current = head;
Node next = null;
Node prev = null;
int count = 0;
/* Reverse first k nodes of linked list */
while (count < k && current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
count++;
}
/* next is now a pointer to (k+1)th node
Recursively call for the list starting from
current. And make rest of the list as next of
first node */
if (next != null)
head.next = reverse(next, k);
// prev is now head of input list
return prev;
}
/* Utility functions */
/* Inserts a new Node at front of the list. */
public void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/* Function to print linked list */
void printList()
{
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
/* Driver program to test above functions */
public static void main(String args[])
{
LinkedList llist = new LinkedList();
/* Constructed Linked List is 1->2->3->4->5->6->
7->8->8->9->null */
llist.push(9);
llist.push(8);
llist.push(7);
llist.push(6);
llist.push(5);
llist.push(4);
llist.push(3);
llist.push(2);
llist.push(1);
System.out.println("Given Linked List");
llist.printList();
llist.head = llist.reverse(llist.head, 3);
System.out.println("Reversed list");
llist.printList();
}
}
/* This code is contributed by Rajat Mishra */
Python3
# Python program to reverse a
# linked list in group of given size
# Node class
class Node:
# Constructor to initialize the node object
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
# Function to initialize head
def __init__(self):
self.head = None
def reverse(self, head, k):
if head == None:
return None
current = head
next = None
prev = None
count = 0
# Reverse first k nodes of the linked list
while(current is not None and count < k):
next = current.next
current.next = prev
prev = current
current = next
count += 1
# next is now a pointer to (k+1)th node
# recursively call for the list starting
# from current. And make rest of the list as
# next of first node
if next is not None:
head.next = self.reverse(next, k)
# prev is new head of the input list
return prev
# Function to insert a new node at the beginning
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
# Utility function to print the linked LinkedList
def printList(self):
temp = self.head
while(temp):
print(temp.data,end=' ')
temp = temp.next
# Driver program
llist = LinkedList()
llist.push(9)
llist.push(8)
llist.push(7)
llist.push(6)
llist.push(5)
llist.push(4)
llist.push(3)
llist.push(2)
llist.push(1)
print("Given linked list")
llist.printList()
llist.head = llist.reverse(llist.head, 3)
print ("\nReversed Linked list")
llist.printList()
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
C#
// C# program to reverse a linked list
// in groups of given size
using System;
public class LinkedList {
Node head; // head of list
/* Linked list Node*/
class Node {
public int data;
public Node next;
public Node(int d)
{
data = d;
next = null;
}
}
Node reverse(Node head, int k)
{
if(head == null)
return null;
Node current = head;
Node next = null;
Node prev = null;
int count = 0;
/* Reverse first k nodes of linked list */
while (count < k && current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
count++;
}
/* next is now a pointer to (k+1)th node
Recursively call for the list starting from
current. And make rest of the list as next of
first node */
if (next != null)
head.next = reverse(next, k);
// prev is now head of input list
return prev;
}
/* Utility functions */
/* Inserts a new Node at front of the list. */
public void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/* Function to print linked list */
void printList()
{
Node temp = head;
while (temp != null) {
Console.Write(temp.data + " ");
temp = temp.next;
}
Console.WriteLine();
}
/* Driver code*/
public static void Main(String[] args)
{
LinkedList llist = new LinkedList();
/* Constructed Linked List is 1->2->3->4->5->6->
7->8->8->9->null */
llist.push(9);
llist.push(8);
llist.push(7);
llist.push(6);
llist.push(5);
llist.push(4);
llist.push(3);
llist.push(2);
llist.push(1);
Console.WriteLine("Given Linked List");
llist.printList();
llist.head = llist.reverse(llist.head, 3);
Console.WriteLine("Reversed list");
llist.printList();
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to reverse a
// linked list in groups of
// given size
var head; // head of list
/* Linked list Node */
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
function reverse(head , k) {
if (head == null)
return null;
var current = head;
var next = null;
var prev = null;
var count = 0;
/* Reverse first k nodes of linked list */
while (count < k && current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
count++;
}
/*
next is now a pointer to (k+1)th node
Recursively call for the list starting
from current. And make rest of the list
as next of first node
*/
if (next != null)
head.next = reverse(next, k);
// prev is now head of input list
return prev;
}
/* Utility functions */
/* Inserts a new Node at front of the list. */
function push(new_data) {
/*
1 & 2: Allocate the Node & Put in the data
*/
new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/* Function to print linked list */
function printList() {
temp = head;
while (temp != null) {
document.write(temp.data + " ");
temp = temp.next;
}
document.write("<br/>");
}
/* Driver program to test above functions */
/*
Constructed Linked List is
1->2->3->4->5->6-> 7->8->8->9->null
*/
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 = reverse(head, 3);
document.write("Reversed list<br/>");
printList();
// This code contributed by gauravrajput1
</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
Análisis de Complejidad:
- Complejidad temporal: O(n).
El recorrido de la lista se realiza solo una vez y tiene ‘n’ elementos. - Espacio Auxiliar: O(n/k).
Para cada Lista Enlazada de tamaño n, n/k o (n/k)+1 se realizarán llamadas durante la recursividad.
Podemos resolver esta pregunta en O(1) Space Complexity.
Enfoque – 2 Espacio optimizado – Iterativo
Los siguientes pasos son necesarios para este algoritmo:
- Cree un Node ficticio y apúntelo al encabezado de entrada, es decir, dummy->next = head.
- Calcule la longitud de la lista enlazada que toma el tiempo O(N), donde N es la longitud de la lista enlazada.
- Inicialice los tres punteros prev, curr, next para invertir k elementos para cada grupo.
- ¡Itera sobre las listas enlazadas hasta el siguiente! = NULL.
- Apunta curr al anterior->siguiente y al lado del curr next.
- Luego, usando el bucle for interno, invierta el grupo en particular usando estos cuatro pasos:
- actual->siguiente = siguiente->siguiente
- siguiente->siguiente = anterior->siguiente
- anterior->siguiente = siguiente
- siguiente = actual->siguiente
7. Este bucle for se ejecuta k-1 veces para todos los grupos excepto el último elemento restante, para el último elemento restante se ejecuta durante la longitud restante de la lista enlazada: 1.
8. Disminuya la cuenta después del ciclo for por k cuenta -= k, para determinar la longitud de la lista enlazada restante.
9. Cambie la posición anterior a actual, anterior = actual.
Aquí está el código para el algoritmo anterior.
C++
// CPP program to reverse a linked list
// in groups of given size
#include <bits/stdc++.h>
using namespace std;
/* Link list node */
class Node {
public:
int data;
Node* next;
};
/* Reverses the linked list in groups
of size k and returns the pointer
to the new head node. */
Node* reverse(Node* head, int k)
{
// If head is NULL or K is 1 then return head
if (!head || k == 1)
return head;
Node* dummy = new Node(); // creating dummy node
dummy->data = -1;
dummy->next = head;
// Initializing three points prev, curr, next
Node *prev = dummy, *curr = dummy, *next = dummy;
// Calculating the length of linked list
int count = 0;
while (curr) {
curr = curr->next;
count++;
}
// Iterating till next is not NULL
while (next) {
// Curr position after every reverse group
curr = prev->next;
// Next will always next to curr
next = curr->next;
// toLoop will set to count - 1 in case of remaining
// element
int toLoop = count > k ? k : count - 1;
for (int i = 1; i < toLoop; i++) {
// 4 steps as discussed above
curr->next = next->next;
next->next = prev->next;
prev->next = next;
next = curr->next;
}
// Setting prev to curr
prev = curr;
// Update count
count -= k;
}
// dummy -> next will be our new head for output linked
// list
return dummy->next;
}
/* UTILITY FUNCTIONS */
/* Function to push a node */
void push(Node** head_ref, 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_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Function to print linked list */
void printList(Node* node)
{
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
}
/* Driver code*/
int main()
{
/* Start with the empty list */
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);
cout << "Given linked list \n";
printList(head);
head = reverse(head, 3);
cout << "\nReversed Linked list \n";
printList(head);
return (0);
}
// This code is contributed by Sania Kumari Gupta
// (kriSania804)
C
// C program to reverse a linked list
// in groups of given size
#include <stdio.h>
#include <stdlib.h>
/* Link list node */
typedef struct Node {
int data;
struct Node* next;
} Node;
// Reverses the linked list in groups of size k and returns
// the pointer to the new head node.
Node* reverse(Node* head, int k)
{
// If head is NULL or K is 1 then return head
if (!head || k == 1)
return head;
// creating dummy node
Node* dummy = (Node*)malloc(sizeof(Node));
dummy->data = -1;
dummy->next = head;
// Initializing three points prev, curr, next
Node *prev = dummy, *curr = dummy, *next = dummy;
// Calculating the length of linked list
int count = 0;
while (curr) {
curr = curr->next;
count++;
}
// Iterating till next is not NULL
while (next) {
// Curr position after every reverse group
curr = prev->next;
// Next will always next to curr
next = curr->next;
// toLoop will set to count - 1 in case of remaining
// element
int toLoop = count > k ? k : count - 1;
for (int i = 1; i < toLoop; i++) {
// 4 steps as discussed above
curr->next = next->next;
next->next = prev->next;
prev->next = next;
next = curr->next;
}
// Setting prev to curr
prev = curr;
// Update count
count -= k;
}
// dummy -> next will be our new head for output linked
// list
return dummy->next;
}
/* UTILITY FUNCTIONS */
/* Function to push a node */
void push(Node** head_ref, int new_data)
{
/* allocate node */
Node* new_node = (Node*)malloc(sizeof(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(Node* node)
{
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
}
/* Driver code*/
int main()
{
/* Start with the empty list */
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("Given linked list \n");
printList(head);
head = reverse(head, 3);
printf("\nReversed Linked list \n");
printList(head);
return (0);
}
// This code is contributed by Sania Kumari Gupta
// (kriSania804)
Java
import java.util.*;
// Linked List Node
class Node {
int data;
Node next;
Node(int a)
{
data = a;
next = null;
}
}
class GFG {
// utility function to insert node in the list
static Node push(Node head, int val)
{
Node newNode = new Node(val);
if (head == null) {
head = newNode;
return head;
}
Node temp = head;
while (temp.next != null)
temp = temp.next;
temp.next = newNode;
return head;
}
// utility function to reverse k nodes in the list
static Node reverse(Node head, int k)
{
// If head is NULL or K is 1 then return head
if (head == null || head.next == null)
return head;
// creating dummy node
Node dummy = new Node(-1);
dummy.next = head;
// Initializing three points prev, curr, next
Node prev = dummy;
Node curr = dummy;
Node next = dummy;
// Calculating the length of linked list
int count = 0;
while (curr != null) {
count++;
curr = curr.next;
}
// Iterating till next is not NULL
while (next != null) {
curr = prev.next; // Curr position after every
// reverse group
next = curr.next; // Next will always next to
// curr
int toLoop
= count > k
? k
: count - 1; // toLoop will set to
// count - 1 in case of
// remaining element
for (int i = 1; i < toLoop; i++) {
// 4 steps as discussed above
curr.next = next.next;
next.next = prev.next;
prev.next = next;
next = curr.next;
}
prev = curr; // Setting prev to curr
count -= k; // Update count
}
return dummy.next; // dummy -> next will be our new
// head for output linked
// list
}
// utility function to print the list
static void print(Node head)
{
while (head.next != null) {
System.out.print(head.data + " ");
head = head.next;
}
System.out.println(head.data);
}
public static void main(String args[])
{
Node head = null;
int k = 3;
head = push(head, 1);
head = push(head, 2);
head = push(head, 3);
head = push(head, 4);
head = push(head, 5);
head = push(head, 6);
head = push(head, 7);
head = push(head, 8);
head = push(head, 9);
System.out.println("Given Linked List");
print(head);
System.out.println("Reversed list");
Node newHead = reverse(head, k);
print(newHead);
}
}
Python3
# Python program to reverse a linked list in groups of given size
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Reverses the linked list in groups
# of size k and returns the pointer
# to the new head node.
def reverse(head, k):
# If head is NULL or K is 1 then return head
if not head or k == 1:
return head
dummy = Node(-1) # creating dummy node
dummy.next = head
# Initializing three points prev, curr, next
prev = dummy
curr = dummy
next = dummy
count = 0
toLoop = 0
i = 0
# Calculating the length of linked list
while curr:
curr = curr.next
count += 1
# Iterating till next is not none
while next:
curr = prev.next # Curr position after every reversed group
next = curr.next # Next will always next to curr
# toLoop will set to count - 1 in case of remaining element
toLoop = count > k and k or count - 1
for i in range(1, toLoop):
# 4 steps as discussed above
curr.next = next.next
next.next = prev.next
prev.next = next
next = curr.next
# Setting prev to curr
prev = curr
# Update count
count -= k
# dummy -> next will be our new head for output linked list
return dummy.next
# Function to print linked list
def printList(node):
while node is not None:
print(node.data, end=" ")
node = node.next
# Created Linked list is 1->2->3->4->5->6->7->8->9
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)
head.next.next.next.next.next = Node(6)
head.next.next.next.next.next.next = Node(7)
head.next.next.next.next.next.next.next = Node(8)
head.next.next.next.next.next.next.next.next = Node(9)
print("Given linked list")
printList(head)
head = reverse(head, 3)
print("\nReversed Linked list")
printList(head)
# This code is contributed by Tapesh(tapeshdua420)
C#
// C# program to reverse a linked list
// in groups of given size
using System;
/* Link list node */
class Node {
public int data;
public Node next;
public Node(int a)
{
data = a;
next = null;
}
}
class GFG {
/* UTILITY FUNCTIONS */
/* Function to push a node */
static Node push(Node head, int val)
{
Node newNode = new Node(val);
if (head == null) {
head = newNode;
return head;
}
Node temp = head;
while (temp.next != null)
temp = temp.next;
temp.next = newNode;
return head;
}
// utility function to reverse k nodes in the list
static Node reverse(Node head, int k)
{
// If head is NULL or K is 1 then return head
if (head == null || head.next == null)
return head;
// creating dummy node
Node dummy = new Node(-1);
dummy.next = head;
// Initializing three points prev, curr, next
Node prev = dummy;
Node curr = dummy;
Node next = dummy;
// Calculating the length of linked list
int count = 0;
while (curr != null) {
count++;
curr = curr.next;
}
// Iterating till next is not NULL
while (next != null) {
curr = prev.next; // Curr position after every
// reverse group
next = curr.next; // Next will always next to
// curr
int toLoop
= count > k
? k
: count - 1; // toLoop will set to
// count - 1 in case of
// remaining element
for (int i = 1; i < toLoop; i++) {
// 4 steps as discussed above
curr.next = next.next;
next.next = prev.next;
prev.next = next;
next = curr.next;
}
prev = curr; // Setting prev to curr
count -= k; // Update count
}
return dummy.next; // dummy -> next will be our new
// head for output linked list
}
// utility function to print the list
static void print(Node head)
{
while (head.next != null) {
Console.Write(head.data + " ");
head = head.next;
}
Console.WriteLine(head.data);
}
public static void Main()
{
Node head = null;
int K = 3;
head = push(head, 1);
head = push(head, 2);
head = push(head, 3);
head = push(head, 4);
head = push(head, 5);
head = push(head, 6);
head = push(head, 7);
head = push(head, 8);
head = push(head, 9);
Console.WriteLine("Given linked list");
print(head);
Console.WriteLine("Reversed Linked list");
Node newHead = reverse(head, K);
print(newHead);
}
}
// This code is contributed by Tapesh (tapeshdua420)
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
Análisis de Complejidad
Complejidad de tiempo: O(N): el ciclo while toma el tiempo O(N/K) y el ciclo for interno toma el tiempo O(K). Entonces N/K * K = N. Por lo tanto TC O(N)
Complejidad espacial: O(1): No se utiliza espacio adicional.
Escriba comentarios si encuentra que el código/algoritmo anterior es incorrecto o encuentra otras formas de resolver el mismo problema.
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