Dada una lista doblemente enlazada que contiene n Nodes. El problema es invertir cada grupo de k Nodes en la lista.
Ejemplos:
Entrada: Lista: 10<->8<->4<->2, K=2
Salida: 8<->10<->2<->4Entrada: Lista: 1<->2<->3<->4<->5<->6<->7<->8, K=3
Salida: 3<->2<->1<- >6<->5<->4<->8<->7
Enfoque recursivo: El enfoque recursivo para resolver este problema se analiza en el Conjunto 1 de este artículo . Aquí, estamos discutiendo el enfoque iterativo.
Enfoque iterativo: este enfoque es una combinación de dos algoritmos: invertir una lista doblemente vinculada e invertir una lista vinculada en un grupo de un tamaño determinado. La función reverseK() invierte individualmente cada lista enlazada de tamaño k y las conecta usando el puntero prevFirst que realiza un seguimiento del Node que vendrá después de la inversión. Siga los pasos a continuación para resolver este problema:
- Si N es menor que igual a 1, devuelve cabeza.
- Inicialice las variables prevFirst como nullptr y curr como head.
- Inicialice la variable firstPass como verdadera.
- Atraviese un ciclo while hasta que curr no sea igual a nulo y realice las siguientes tareas:
- Inicialice la cuenta variable como 0 .
- Inicialice las variables primero como curr, next y prev como nulo.
- Atraviese un ciclo while hasta que curr no sea igual a nulo y count sea menor que K y realice las siguientes tareas:
- Establezca el valor de siguiente como actual->siguiente.
- Si el conteo es igual a 0 , establezca actual->siguiente como nulo ; de lo contrario, actual->siguiente como actual->anterior.
- Establezca curr->prev como siguiente, prev como curr y curr como siguiente.
- Aumente el valor de la cuenta en 1.
- Si firstPass es verdadero , establezca head como next->prev y firstPass como falso.
- De lo contrario, establezca anteriorPrimero->siguiente como anterior.
- Establecer prevFirst como primero.
- Después de realizar los pasos anteriores, imprima el valor de cabeza como respuesta.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// A linked list node
class Node {
public:
int data;
Node* next;
Node* prev;
};
// Given a reference (pointer to pointer)
// to the head of a list
// and an int, inserts a new node on the
// front of the 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;
// Make next of new node as head
// and previous as NULL
new_node->next = (*head_ref);
new_node->prev = NULL;
// Change prev of head node to new node
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
// Move the head to point to the new node
(*head_ref) = new_node;
}
// Given a node as prev_node, insert
// a new node after the given node
void insertAfter(Node* prev_node, int new_data)
{
// Check if the given prev_node is NULL
if (prev_node == NULL) {
cout << "the given previous "
<< "node cannot be NULL";
return;
}
// Allocate new node
Node* new_node = new Node();
// Put in the data
new_node->data = new_data;
// Make next of new node as next of prev_node
new_node->next = prev_node->next;
// Make the next of prev_node as new_node
prev_node->next = new_node;
// Make prev_node as previous of new_node
new_node->prev = prev_node;
// Change previous of new_node's next node
if (new_node->next != NULL)
new_node->next->prev = new_node;
}
// Given a reference (pointer to pointer) to the head
// of a DLL and an int, appends a new node at the end
void append(Node** head_ref, int new_data)
{
// Allocate node
Node* new_node = new Node();
Node* last = *head_ref;
// Put in the data
new_node->data = new_data;
// This new node is going to be the last node,
// so make next of it as NULL
new_node->next = NULL;
// If the Linked List is empty,
// then make the new
// node as head
if (*head_ref == NULL) {
new_node->prev = NULL;
*head_ref = new_node;
return;
}
// Else traverse till the last node
while (last->next != NULL)
last = last->next;
// Change the next of last node
last->next = new_node;
// Make last node as previous of new node
new_node->prev = last;
return;
}
// This function prints contents of
// linked list starting from the given node
void printList(Node* node)
{
Node* last;
while (node != NULL) {
cout << " " << node->data << " ";
last = node;
node = node->next;
}
}
Node* reverseK(Node* head, int k)
{
// When head is NULL or linked list
// has a single node we return
if (head == NULL || head->next == NULL)
return head;
// PrevFirst pointer keeps track of
// the node that is to be connected to each
// reversed part.
Node *prevFirst = NULL, *curr = head;
// FirstPass variable is used so that we
// can mark head of the new linkedlist.
bool firstPass = true;
while (curr != NULL) {
int count = 0;
// Next keeps track of the next node of curr
// Prev keeps track of the previous node of curr
Node *first = curr, *next = NULL, *prev = NULL;
while (curr != NULL && count < k) {
// Reversing the doubly linked list by just
// swapping their next and prev pointers
next = curr->next;
if (count == 0)
curr->next = NULL;
else
curr->next = curr->prev;
curr->prev = next;
prev = curr;
curr = next;
count++;
}
if (firstPass) {
// Setting the head of the new linkedlist
head = next->prev;
firstPass = false;
}
else {
prevFirst->next = prev;
}
prevFirst = first;
}
return head;
}
// Driver Code
int main()
{
// Start with the empty list
Node* head = NULL;
// Insert 6. So linked list becomes 6->NULL
append(&head, 6);
// Insert 7 at the beginning. So
// linked list becomes 7->6->NULL
push(&head, 7);
// Insert 1 at the beginning. So
// linked list becomes 1->7->6->NULL
push(&head, 1);
// Insert 4 at the end. So linked
// list becomes 1->7->6->4->NULL
append(&head, 4);
// Insert 8, after 7. So linked
// list becomes 1->7->8->6->4->NULL
insertAfter(head->next, 8);
// list becomes 1->7->8->6->4->9->NULL
append(&head, 9);
head = reverseK(head, 2);
printList(head);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// A linked list node
static class Node {
int data;
Node next;
Node prev;
};
static Node head = null;
// Given a reference (pointer to pointer)
// to the head of a list
// and an int, inserts a new node on the
// front of the list.
static void push(int new_data)
{
// Allocate node
Node new_node = new Node();
// Put in the data
new_node.data = new_data;
// Make next of new node as head
// and previous as null
new_node.next = head;
new_node.prev = null;
// Change prev of head node to new node
if (head != null)
head.prev = new_node;
// Move the head to point to the new node
head = new_node;
}
// Given a node as prev_node, insert
// a new node after the given node
static void insertAfter(Node prev_node, int new_data)
{
// Check if the given prev_node is null
if (prev_node == null) {
System.out.print("the given previous "
+ "node cannot be null");
return;
}
// Allocate new node
Node new_node = new Node();
// Put in the data
new_node.data = new_data;
// Make next of new node as next of prev_node
new_node.next = prev_node.next;
// Make the next of prev_node as new_node
prev_node.next = new_node;
// Make prev_node as previous of new_node
new_node.prev = prev_node;
// Change previous of new_node's next node
if (new_node.next != null)
new_node.next.prev = new_node;
}
// Given a reference (pointer to pointer) to the head
// of a DLL and an int, appends a new node at the end
static void append(int new_data)
{
// Allocate node
Node new_node = new Node();
Node last = head;
// Put in the data
new_node.data = new_data;
// This new node is going to be the last node,
// so make next of it as null
new_node.next = null;
// If the Linked List is empty,
// then make the new
// node as head
if (head == null) {
new_node.prev = null;
head = new_node;
return;
}
// Else traverse till the last node
while (last.next != null)
last = last.next;
// Change the next of last node
last.next = new_node;
// Make last node as previous of new node
new_node.prev = last;
return;
}
// This function prints contents of
// linked list starting from the given node
static void printList(Node node)
{
Node last = new Node();
while (node != null) {
System.out.print(" " + node.data+ " ");
last = node;
node = node.next;
}
}
static Node reverseK(Node head, int k)
{
// When head is null or linked list
// has a single node we return
if (head == null || head.next == null)
return head;
// PrevFirst pointer keeps track of
// the node that is to be connected to each
// reversed part.
Node prevFirst = null, curr = head;
// FirstPass variable is used so that we
// can mark head of the new linkedlist.
boolean firstPass = true;
while (curr != null) {
int count = 0;
// Next keeps track of the next node of curr
// Prev keeps track of the previous node of curr
Node first = curr, next = null, prev = null;
while (curr != null && count < k) {
// Reversing the doubly linked list by just
// swapping their next and prev pointers
next = curr.next;
if (count == 0)
curr.next = null;
else
curr.next = curr.prev;
curr.prev = next;
prev = curr;
curr = next;
count++;
}
if (firstPass) {
// Setting the head of the new linkedlist
head = next.prev;
firstPass = false;
}
else {
prevFirst.next = prev;
}
prevFirst = first;
}
return head;
}
// Driver Code
public static void main(String[] args)
{
// Start with the empty list
head = null;
// Insert 6. So linked list becomes 6.null
append( 6);
// Insert 7 at the beginning. So
// linked list becomes 7.6.null
push(7);
// Insert 1 at the beginning. So
// linked list becomes 1.7.6.null
push(1);
// Insert 4 at the end. So linked
// list becomes 1.7.6.4.null
append( 4);
// Insert 8, after 7. So linked
// list becomes 1.7.8.6.4.null
insertAfter(head.next, 8);
// list becomes 1.7.8.6.4.9.null
append( 9);
head = reverseK(head, 2);
printList(head);
}
}
// This code contributed by shikhasingrajput
Python3
# Python Code for the above problem. # Node class class Node: # Function to initialise the node object def __init__(self, data): self.data = data # Assign data self.next = None # Initialize next as null self.prev = None # Initialize previous as null # Linked List class contains a Node object class LinkedList: # Function to initialize head def __init__(self): self.head = None # Function to insert a new node at the beginning def push(self, new_data): new_node = Node(new_data) new_node.next = self.head new_node.prev = None if self.head is not None: self.head.prev = new_node self.head = new_node # This function is in LinkedList class. Inserts a # new node after the given prev_node. def insertAfter(self, prev_node, new_data): if prev_node is None: return new_node = Node(new_data) new_node.next = prev_node.next prev_node.next = new_node new_node.prev = prev_node if new_node.next is not None: new_node.next.prev = new_node # This function is defined in Linked List class # Appends a new node at the end. def append(self, new_data): new_node = Node(new_data) last = self.head if self.head is None: new_node.prev = None self.head = new_node return while (last.next): last = last.next last.next = new_node new_node.prev = last # Utility function to print the linked list def printList(self): temp = self.head while(temp): print(temp.data, end=" ") temp = temp.next def reverseK(self, k): # When head is NULL or linked list # has a single node we return if self.head is None or self.head.next is None: return # PrevFirst pointer keeps track of # the node that is to be connected to each # reversed part. prevFirst, curr = None, self.head # FirstPass variable is used so that we # can mark head of the new linkedlist. firstPass = True while curr: count = 0 # Next keeps track of the next node of curr # Prev keeps track of the previous node of curr first, next_node, prev_node = curr, None, None while curr is not None and count < k: # Reversing the doubly linked list by just # swapping their next and prev pointers next_node = curr.next if count is 0: curr.next = None else: curr.next = curr.prev curr.prev = next_node prev_node = curr curr = next_node count += 1 if (firstPass): # Setting the head of the new linkedlist self.head = next_node.prev firstPass = False else: prevFirst.next = prev_node prevFirst = first return self.head if __name__ == '__main__': llist = LinkedList() # Insert 6. So linked list becomes 6->NULL llist.append(6) # Insert 7 at the beginning. So # linked list becomes 7->6->NULL llist.push(7) # Insert 1 at the beginning. So # linked list becomes 1->7->6->NULL llist.push(1) # Insert 4 at the end. So linked # list becomes 1->7->6->4->NULL llist.append(4) # Insert 8, after 7. So linked # list becomes 1->7->8->6->4->NULL llist.insertAfter(llist.head.next, 8) # list becomes 1->7->8->6->4->9->NULL llist.append(9) llist.reverseK(2) llist.printList() # This code is contributed by lokesh (lokeshmvs21).
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG{
// A linked list node
class Node {
public int data;
public Node next;
public Node prev;
};
static Node head = null;
// Given a reference (pointer to pointer)
// to the head of a list
// and an int, inserts a new node on the
// front of the list.
static void push(int new_data)
{
// Allocate node
Node new_node = new Node();
// Put in the data
new_node.data = new_data;
// Make next of new node as head
// and previous as null
new_node.next = head;
new_node.prev = null;
// Change prev of head node to new node
if (head != null)
head.prev = new_node;
// Move the head to point to the new node
head = new_node;
}
// Given a node as prev_node, insert
// a new node after the given node
static void insertAfter(Node prev_node, int new_data)
{
// Check if the given prev_node is null
if (prev_node == null) {
Console.Write("the given previous "
+ "node cannot be null");
return;
}
// Allocate new node
Node new_node = new Node();
// Put in the data
new_node.data = new_data;
// Make next of new node as next of prev_node
new_node.next = prev_node.next;
// Make the next of prev_node as new_node
prev_node.next = new_node;
// Make prev_node as previous of new_node
new_node.prev = prev_node;
// Change previous of new_node's next node
if (new_node.next != null)
new_node.next.prev = new_node;
}
// Given a reference (pointer to pointer) to the head
// of a DLL and an int, appends a new node at the end
static void append(int new_data)
{
// Allocate node
Node new_node = new Node();
Node last = head;
// Put in the data
new_node.data = new_data;
// This new node is going to be the last node,
// so make next of it as null
new_node.next = null;
// If the Linked List is empty,
// then make the new
// node as head
if (head == null) {
new_node.prev = null;
head = new_node;
return;
}
// Else traverse till the last node
while (last.next != null)
last = last.next;
// Change the next of last node
last.next = new_node;
// Make last node as previous of new node
new_node.prev = last;
return;
}
// This function prints contents of
// linked list starting from the given node
static void printList(Node node)
{
Node last = new Node();
while (node != null) {
Console.Write(" " + node.data+ " ");
last = node;
node = node.next;
}
}
static Node reverseK(Node head, int k)
{
// When head is null or linked list
// has a single node we return
if (head == null || head.next == null)
return head;
// PrevFirst pointer keeps track of
// the node that is to be connected to each
// reversed part.
Node prevFirst = null, curr = head;
// FirstPass variable is used so that we
// can mark head of the new linkedlist.
bool firstPass = true;
while (curr != null) {
int count = 0;
// Next keeps track of the next node of curr
// Prev keeps track of the previous node of curr
Node first = curr, next = null, prev = null;
while (curr != null && count < k) {
// Reversing the doubly linked list by just
// swapping their next and prev pointers
next = curr.next;
if (count == 0)
curr.next = null;
else
curr.next = curr.prev;
curr.prev = next;
prev = curr;
curr = next;
count++;
}
if (firstPass) {
// Setting the head of the new linkedlist
head = next.prev;
firstPass = false;
}
else {
prevFirst.next = prev;
}
prevFirst = first;
}
return head;
}
// Driver Code
public static void Main(String[] args)
{
// Start with the empty list
head = null;
// Insert 6. So linked list becomes 6.null
append( 6);
// Insert 7 at the beginning. So
// linked list becomes 7.6.null
push(7);
// Insert 1 at the beginning. So
// linked list becomes 1.7.6.null
push(1);
// Insert 4 at the end. So linked
// list becomes 1.7.6.4.null
append( 4);
// Insert 8, after 7. So linked
// list becomes 1.7.8.6.4.null
insertAfter(head.next, 8);
// list becomes 1.7.8.6.4.9.null
append( 9);
head = reverseK(head, 2);
printList(head);
}
}
// This code is contributed by 29AjayKumar
Producción
7 1 6 8 9 4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por 8769063451sanecha y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA