Dada una lista enlazada y un número entero K , la tarea es invertir todos los K Nodes de la lista enlazada dada.
Ejemplos:
Entrada: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> NULO, K = 3
Salida: 3 2 1 6 5 4 8 7Entrada: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> NULO, K = 5
Salida: 5 4 3 2 1 8 7 6
Enfoque: Ya hemos discutido una solución recursiva en las publicaciones Conjunto 1 y Conjunto 2 . En esta publicación, discutiremos una solución iterativa al problema anterior. A diferencia de las soluciones anteriores, no usamos ninguna forma de la pila para implementar nuestra solución. Invertimos los primeros k Nodes de la lista enlazada. Mientras invertimos, hacemos un seguimiento del primer y último Node de la lista enlazada k-invertida usando el puntero de unión y cola. Después de invertir los k Nodes de la lista enlazada, unimos los Nodes señalados por el puntero de cola y el puntero de unión y los actualizamos. Repetimos este proceso hasta que todos los grupos de Nodes estén invertidos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Link list node
struct Node {
int data;
struct Node* next;
};
/* Function to reverse the linked list in groups of
size k and return the pointer to the new head node. */
Node* reverse(struct Node* head, int k)
{
Node* prev = NULL;
Node* curr = head;
Node* temp = NULL;
Node* tail = NULL;
Node* newHead = NULL;
Node* join = NULL;
int t = 0;
// Traverse till the end of the linked list
while (curr) {
t = k;
join = curr;
prev = NULL;
// Reverse group of k nodes of the linked list
while (curr && t--) {
temp = curr->next;
curr->next = prev;
prev = curr;
curr = temp;
}
// Sets the new head of the input list
if (!newHead)
newHead = prev;
/* Tail pointer keeps track of the last node
of the k-reversed linked list. We join the
tail pointer with the head of the next
k-reversed linked list's head */
if (tail)
tail->next = prev;
/* The tail is then updated to the last node
of the next k-reverse linked list */
tail = join;
}
/* newHead is new head of the input list */
return newHead;
}
// Function to insert a node at
// the head of the linked list
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 the 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);
int k = 3;
cout << "Given linked list \n";
printList(head);
head = reverse(head, k);
cout << "\nReversed Linked list \n";
printList(head);
return (0);
}
Java
// Java implementation of the approach
class GFG
{
// Link list node
static class Node
{
int data;
Node next;
};
// Function to reverse the linked list in groups of
//size k and return the pointer to the new head node. /
static Node reverse( Node head, int k)
{
Node prev = null;
Node curr = head;
Node temp = null;
Node tail = null;
Node newHead = null;
Node join = null;
int t = 0;
// Traverse till the end of the linked list
while (curr != null)
{
t = k;
join = curr;
prev = null;
// Reverse group of k nodes of the linked list
while (curr != null && t-- != 0)
{
temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
// Sets the new head of the input list
if ((newHead == null))
newHead = prev;
/* Tail pointer keeps track of the last node
of the k-reversed linked list. We join the
tail pointer with the head of the next
k-reversed linked list's head */
if (tail != null)
tail.next = prev;
/* The tail is then updated to the last node
of the next k-reverse linked list */
tail = join;
}
// newHead is new head of the input list /
return newHead;
}
// Function to insert a node at
// the head of the linked list
static Node 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;
return head_ref;
}
// Function to print the 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
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);
int k = 3;
System.out.print( "Given linked list \n");
printList(head);
head = reverse(head, k);
System.out.print( "\nReversed Linked list \n");
printList(head);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 implementation of the approach
import math
# Link list node
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to reverse the linked list in groups of
#size k and return the pointer to the new head node.
def reverse(head, k) :
prev = None
curr = head
temp = None
tail = None
newHead = None
join = None
t = 0
# Traverse till the end of the linked list
while (curr) :
t = k
join = curr
prev = None
# Reverse group of k nodes of the linked list
while (curr and t > 0):
temp = curr.next
curr.next = prev
prev = curr
curr = temp
t = t - 1
# Sets the new head of the input list
if (newHead == None):
newHead = prev
# Tail pointer keeps track of the last node
# of the k-reversed linked list. We join the
# tail pointer with the head of the next
# k-reversed linked list's head
if (tail != None):
tail.next = prev
# The tail is then updated to the last node
# of the next k-reverse linked list
tail = join
# newHead is new head of the input list */
return newHead
# Function to insert a node at
# the head of the linked list
def push(head_ref, new_data) :
# allocate node */
new_node =Node(new_data)
# 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 the linked list
def printList(node):
while (node != None) :
print(node.data, end = " ")
node = node.next
# Driver code
if __name__=='__main__':
# Start with the empty list
head = None
# Created Linked list is
# 1.2.3.4.5.6.7.8.9
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)
k = 3
print("Given linked list ")
printList(head)
head = reverse(head, k)
print("\nReversed Linked list ")
printList(head)
# This code is contributed by Srathore
C#
// C# implementation of the approach
using System;
class GFG
{
// Link list node
public class Node
{
public int data;
public Node next;
};
// Function to reverse the linked list in groups of
//size k and return the pointer to the new head node. /
static Node reverse( Node head, int k)
{
Node prev = null;
Node curr = head;
Node temp = null;
Node tail = null;
Node newHead = null;
Node join = null;
int t = 0;
// Traverse till the end of the linked list
while (curr != null)
{
t = k;
join = curr;
prev = null;
// Reverse group of k nodes of the linked list
while (curr != null && t-- != 0)
{
temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
// Sets the new head of the input list
if ((newHead == null))
newHead = prev;
/* Tail pointer keeps track of the last node
of the k-reversed linked list. We join the
tail pointer with the head of the next
k-reversed linked list's head */
if (tail != null)
tail.next = prev;
/* The tail is then updated to the last node
of the next k-reverse linked list */
tail = join;
}
// newHead is new head of the input list /
return newHead;
}
// Function to insert a node at
// the head of the linked list
static Node 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;
return head_ref;
}
// Function to print the 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
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);
int k = 3;
Console.Write( "Given linked list \n");
printList(head);
head = reverse(head, k);
Console.Write( "\nReversed Linked list \n");
printList(head);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the approach
// Link list node
class Node
{
constructor()
{
this.data = 0;
this.next = null;
}
};
// Function to reverse the linked list
// in groups of size k and return the
// pointer to the new head node.
function reverse(head, k)
{
var prev = null;
var curr = head;
var temp = null;
var tail = null;
var newHead = null;
var join = null;
var t = 0;
// Traverse till the end of the linked list
while (curr != null)
{
t = k;
join = curr;
prev = null;
// Reverse group of k nodes of the linked list
while (curr != null && t-- != 0)
{
temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
// Sets the new head of the input list
if ((newHead == null))
newHead = prev;
/* Tail pointer keeps track of the last node
of the k-reversed linked list. We join the
tail pointer with the head of the next
k-reversed linked list's head */
if (tail != null)
tail.next = prev;
/* The tail is then updated to the last node
of the next k-reverse linked list */
tail = join;
}
// newHead is new head of the input list
return newHead;
}
// Function to insert a node at
// the head of the linked list
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 the linked list
function printList(node)
{
while (node != null)
{
document.write( node.data + " ");
node = node.next;
}
}
// Driver code
// Start with the empty list
var head = null;
// Created Linked list is
// 1.2.3.4.5.6.7.8.9
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);
var k = 3;
document.write("Given linked list <br>");
printList(head);
head = reverse(head, k);
document.write("<br>Reversed Linked list <br>");
printList(head);
// This code is contributed by itsok
</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 de tiempo: O(n) donde n es el número de Nodes en la lista dada.
Complejidad espacial: O(1)