Dada una lista enlazada y un número entero K , la tarea es invertir todos los Nodes K alternativos.
Ejemplos:
Entrada: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> NULO, K = 3
Salida: 3 2 1 4 5 6 9 8 7
Entrada: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> NULO, K = 5
Salida: 5 4 3 2 1 6 7 8 9
Enfoque: Ya hemos discutido una solución recursiva aquí . En esta publicación, discutiremos una solución iterativa al problema anterior. Mientras recorremos, procesamos 2k Nodes en una iteración y realizamos un seguimiento del primer y último Node del grupo de k-Nodes en la lista vinculada dada usando el puntero de unión y cola. Después de invertir los k Nodes de la lista enlazada, unimos el último Node de la lista invertida, señalado por el puntero de cola, con el primer Node de la lista original, señalado por el puntero de unión. Luego movemos el puntero actual hasta que saltemos los siguientes k Nodes.
La cola ahora se convierte en el último Node de la lista normal (que apunta el puntero de cola actualizado) y los puntos de unión al primero de la lista invertida y luego se unen. Repetimos este proceso hasta que todos los Nodes se procesen de la misma manera.
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
class Node {
public:
int data;
Node* next;
};
/* Function to reverse alternate k nodes and
return the pointer to the new head node */
Node* kAltReverse(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 alternative group of k nodes
// of the given 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. The tail pointer
is then joined with the first node of the
next k-nodes of the linked list */
if (tail)
tail->next = prev;
tail = join;
tail->next = curr;
t = k;
/* Traverse through the next k nodes
which will not be reversed */
while (curr && t--) {
prev = curr;
curr = curr->next;
}
/* Tail pointer keeps track of the last
node of the k nodes traversed above */
tail = prev;
}
// newHead is new head of the modified 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)
{
int count = 0;
while (node != NULL) {
cout << node->data << " ";
node = node->next;
count++;
}
}
// Driver code
int main(void)
{
// Start with the empty list
Node* head = NULL;
int i;
// Create a list 1->2->3->4->...->10
for (i = 10; i > 0; i--)
push(&head, i);
int k = 3;
cout << "Given linked list \n";
printList(head);
head = kAltReverse(head, k);
cout << "\n Modified 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;
};
static Node head;
/* Function to reverse alternate k nodes and
return the pointer to the new head node */
static Node kAltReverse(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 alternative group of k nodes
// of the given 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. The tail pointer
is then joined with the first node of the
next k-nodes of the linked list */
if (tail != null)
tail.next = prev;
tail = join;
tail.next = curr;
t = k;
/* Traverse through the next k nodes
which will not be reversed */
while (curr != null && t-- >0)
{
prev = curr;
curr = curr.next;
}
/* Tail pointer keeps track of the last
node of the k nodes traversed above */
tail = prev;
}
// newHead is new head of the modified list
return newHead;
}
// Function to insert a node at
// the head of the linked list
static 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;
head = head_ref;
}
// Function to print the linked list
static void printList(Node node)
{
int count = 0;
while (node != null)
{
System.out.print(node.data + " ");
node = node.next;
count++;
}
}
// Driver code
public static void main(String[] args)
{
// Start with the empty list
head = null;
int i;
// Create a list 1->2->3->4->...->10
for (i = 10; i > 0; i--)
push(head, i);
int k = 3;
System.out.print("Given linked list \n");
printList(head);
head = kAltReverse(head, k);
System.out.print("\n Modified Linked list \n");
printList(head);
}
}
// This code is contributed by Rajput-Ji
Python
# Python implementation of the approach
# Node class
class Node:
# Function to initialise the node object
def __init__(self, data):
self.data = data # Assign data
self.next = None
head = None
# Function to reverse alternate k nodes and
# return the pointer to the new head node
def kAltReverse(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 != None) :
t = k
join = curr
prev = None
# Reverse alternative group of k nodes
# of the given linked list
while (curr != None and t > 0):
t = t - 1
temp = curr.next
curr.next = prev
prev = curr
curr = temp
# 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. The tail pointer
# is then joined with the first node of the
# next k-nodes of the linked list
if (tail != None):
tail.next = prev
tail = join
tail.next = curr
t = k
# Traverse through the next k nodes
# which will not be reversed
while (curr != None and t > 0):
t = t - 1
prev = curr
curr = curr.next
# Tail pointer keeps track of the last
# node of the k nodes traversed above
tail = prev
# newHead is new head of the modified list
return newHead
# Function to insert a node at
# the head of the linked list
def push(head_ref, new_data):
global head
# allocate node
new_node = Node(0)
# 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
head = head_ref
# Function to print the linked list
def printList(node):
count = 0
while (node != None):
print(node.data ,end= " ")
node = node.next
count = count + 1
# Driver code
# Start with the empty list
head = None
i = 10
# Create a list 1->2->3->4->...->10
while ( i > 0 ):
push(head, i)
i = i - 1
k = 3
print("Given linked list ")
printList(head)
head = kAltReverse(head, k)
print("\n Modified Linked list ")
printList(head)
# This code is contributed by Arnab Kundu
C#
// C# implementation of the approach
using System;
class GFG
{
// Link list node
public class Node
{
public int data;
public Node next;
};
static Node head;
/* Function to reverse alternate k nodes and
return the pointer to the new head node */
static Node kAltReverse(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 alternative group of k nodes
// of the given 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. The tail pointer
is then joined with the first node of the
next k-nodes of the linked list */
if (tail != null)
tail.next = prev;
tail = join;
tail.next = curr;
t = k;
/* Traverse through the next k nodes
which will not be reversed */
while (curr != null && t-- >0)
{
prev = curr;
curr = curr.next;
}
/* Tail pointer keeps track of the last
node of the k nodes traversed above */
tail = prev;
}
// newHead is new head of the modified list
return newHead;
}
// Function to insert a node at
// the head of the linked list
static 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;
head = head_ref;
}
// Function to print the linked list
static void printList(Node node)
{
int count = 0;
while (node != null)
{
Console.Write(node.data + " ");
node = node.next;
count++;
}
}
// Driver code
public static void Main(String[] args)
{
// Start with the empty list
head = null;
int i;
// Create a list 1->2->3->4->...->10
for (i = 10; i > 0; i--)
push(head, i);
int k = 3;
Console.Write("Given linked list \n");
printList(head);
head = kAltReverse(head, k);
Console.Write("\nModified Linked list \n");
printList(head);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// javascript implementation of the approach // Link list node
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
var head;
/*
* Function to reverse alternate k nodes and return the pointer to the new head
* node
*/
function kAltReverse(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 alternative group of k nodes // of the given 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. The
* tail pointer is then joined with the first node of the next k-nodes of the
* linked list
*/
if (tail != null)
tail.next = prev;
tail = join;
tail.next = curr;
t = k;
/*
* Traverse through the next k nodes which will not be reversed
*/
while (curr != null && t-- > 0) {
prev = curr;
curr = curr.next;
}
/*
* Tail pointer keeps track of the last node of the k nodes traversed above
*/
tail = prev;
}
// newHead is new head of the modified 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;
head = head_ref;
}
// Function to print the linked list
function printList(node) {
var count = 0;
while (node != null) {
document.write(node.data + " ");
node = node.next;
count++;
}
}
// Driver code
// Start with the empty list
head = null;
var i;
// Create a list 1->2->3->4->...->10
for (i = 10; i > 0; i--)
push(head, i);
var k = 3;
document.write("Given linked list <br/>");
printList(head);
head = kAltReverse(head, k);
document.write("<br/>Modified Linked list <br/>");
printList(head);
// This code contributed by gauravrajput1
</script>
Producción:
Given linked list 1 2 3 4 5 6 7 8 9 10 Modified Linked list 3 2 1 4 5 6 9 8 7 10
Complejidad de tiempo: O(n)
Complejidad de espacio: O(1)