Dada una lista doblemente enlazada que contiene n Nodes. El problema es invertir cada grupo de k Nodes en la lista.
Ejemplos:
Requisito previo: invertir una lista doblemente enlazada | Conjunto-2.
Enfoque: Cree una función recursiva, digamos reverse(head, k) . Esta función recibe la cabecera o el primer Node de cada grupo de k Nodes. Invierte esos grupos de k Nodes aplicando el enfoque discutido en Invertir una lista doblemente enlazada | Conjunto-2. Después de invertir el grupo de k Nodes, la función verifica si el siguiente grupo de Nodes existe en la lista o no. Si existe un grupo, realiza una llamada recursiva a sí mismo con el primer Node del siguiente grupo y realiza los ajustes necesarios con los enlaces anterior y siguiente de ese grupo. Finalmente, devuelve el nuevo Node principal del grupo invertido.
C++
// C++ implementation to reverse a doubly linked list
// in groups of given size
#include <bits/stdc++.h>
using namespace std;
// a node of the doubly linked list
struct Node {
int data;
Node *next, *prev;
};
// function to get a new node
Node* getNode(int data)
{
// allocate space
Node* new_node = (Node*)malloc(sizeof(Node));
// put in the data
new_node->data = data;
new_node->next = new_node->prev = NULL;
return new_node;
}
// function to insert a node at the beginning
// of the Doubly Linked List
void push(Node** head_ref, Node* new_node)
{
// since we are adding at the beginning,
// prev is always NULL
new_node->prev = NULL;
// link the old list off the new node
new_node->next = (*head_ref);
// 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;
}
// function to reverse a doubly linked list
// in groups of given size
Node* revListInGroupOfGivenSize(Node* head, int k)
{
Node *current = head;
Node* next = NULL;
Node* newHead = NULL;
int count = 0;
// reversing the current group of k
// or less than k nodes by adding
// them at the beginning of list
// 'newHead'
while (current != NULL && count < k)
{
next = current->next;
push(&newHead, current);
current = next;
count++;
}
// if next group exists then making the desired
// adjustments in the link
if (next != NULL)
{
head->next = revListInGroupOfGivenSize(next, k);
head->next->prev = head;
}
// pointer to the new head of the
// reversed group
// pointer to the new head should point to NULL, otherwise you won't be able to traverse list in reverse order using 'prev'
newHead->prev = NULL;
return newHead;
}
// Function to print nodes in a
// given doubly linked list
void printList(Node* head)
{
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
}
// Driver program to test above
int main()
{
// Start with the empty list
Node* head = NULL;
// Create doubly linked: 10<->8<->4<->2
push(&head, getNode(2));
push(&head, getNode(4));
push(&head, getNode(8));
push(&head, getNode(10));
int k = 2;
cout << "Original list: ";
printList(head);
// Reverse doubly linked list in groups of
// size 'k'
head = revListInGroupOfGivenSize(head, k);
cout << "\nModified list: ";
printList(head);
return 0;
}
Java
// Java implementation to reverse a doubly linked list
// in groups of given size
import java.io.*;
import java.util.*;
// Represents a node of doubly linked list
class Node
{
int data;
Node next, prev;
}
class GFG
{
// function to get a new node
static Node getNode(int data)
{
// allocating node
Node new_node = new Node();
new_node.data = data;
new_node.next = new_node.prev = null;
return new_node;
}
// function to insert a node at the beginning
// of the Doubly Linked List
static Node push(Node head, Node new_node)
{
// since we are adding at the beginning,
// prev is always NULL
new_node.prev = null;
// link the old list off the new node
new_node.next = head;
// 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;
return head;
}
// function to reverse a doubly linked list
// in groups of given size
static Node revListInGroupOfGivenSize(Node head, int k)
{
Node current = head;
Node next = null;
Node newHead = null;
int count = 0;
// reversing the current group of k
// or less than k nodes by adding
// them at the beginning of list
// 'newHead'
while (current != null && count < k)
{
next = current.next;
newHead = push(newHead, current);
current = next;
count++;
}
// if next group exists then making the desired
// adjustments in the link
if (next != null)
{
head.next = revListInGroupOfGivenSize(next, k);
head.next.prev = head;
}
// pointer to the new head of the
// reversed group
return newHead;
}
// Function to print nodes in a
// given doubly linked list
static void printList(Node head)
{
while (head != null)
{
System.out.print(head.data + " ");
head = head.next;
}
}
// Driver code
public static void main(String args[])
{
// Start with the empty list
Node head = null;
// Create doubly linked: 10<->8<->4<->2
head = push(head, getNode(2));
head = push(head, getNode(4));
head = push(head, getNode(8));
head = push(head, getNode(10));
int k = 2;
System.out.print("Original list: ");
printList(head);
// Reverse doubly linked list in groups of
// size 'k'
head = revListInGroupOfGivenSize(head, k);
System.out.print("\nModified list: ");
printList(head);
}
}
// This code is contributed by rachana soma
Python3
# Python implementation to reverse a doubly linked list
# in groups of given size
# Link list node
class Node:
def __init__(self, data):
self.data = data
self.next = next
# function to get a new node
def getNode(data):
# allocate space
new_node = Node(0)
# put in the data
new_node.data = data
new_node.next = new_node.prev = None
return new_node
# function to insert a node at the beginning
# of the Doubly Linked List
def push(head_ref, new_node):
# since we are adding at the beginning,
# prev is always None
new_node.prev = None
# link the old list off the new node
new_node.next = (head_ref)
# change prev of head node to new node
if ((head_ref) != None):
(head_ref).prev = new_node
# move the head to point to the new node
(head_ref) = new_node
return head_ref
# function to reverse a doubly linked list
# in groups of given size
def revListInGroupOfGivenSize( head, k):
current = head
next = None
newHead = None
count = 0
# reversing the current group of k
# or less than k nodes by adding
# them at the beginning of list
# 'newHead'
while (current != None and count < k):
next = current.next
newHead = push(newHead, current)
current = next
count = count + 1
# if next group exists then making the desired
# adjustments in the link
if (next != None):
head.next = revListInGroupOfGivenSize(next, k)
head.next.prev = head
# pointer to the new head of the
# reversed group
return newHead
# Function to print nodes in a
# given doubly linked list
def printList(head):
while (head != None):
print( head.data , end=" ")
head = head.next
# Driver program to test above
# Start with the empty list
head = None
# Create doubly linked: 10<.8<.4<.2
head = push(head, getNode(2))
head = push(head, getNode(4))
head = push(head, getNode(8))
head = push(head, getNode(10))
k = 2
print("Original list: ")
printList(head)
# Reverse doubly linked list in groups of
# size 'k'
head = revListInGroupOfGivenSize(head, k)
print("\nModified list: ")
printList(head)
# This code is contributed by Arnab Kundu
C#
// C# implementation to reverse a doubly linked list
// in groups of given size
using System;
// Represents a node of doubly linked list
public class Node
{
public int data;
public Node next, prev;
}
class GFG
{
// function to get a new node
static Node getNode(int data)
{
// allocating node
Node new_node = new Node();
new_node.data = data;
new_node.next = new_node.prev = null;
return new_node;
}
// function to insert a node at the beginning
// of the Doubly Linked List
static Node push(Node head, Node new_node)
{
// since we are adding at the beginning,
// prev is always NULL
new_node.prev = null;
// link the old list off the new node
new_node.next = head;
// 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;
return head;
}
// function to reverse a doubly linked list
// in groups of given size
static Node revListInGroupOfGivenSize(Node head, int k)
{
Node current = head;
Node next = null;
Node newHead = null;
int count = 0;
// reversing the current group of k
// or less than k nodes by adding
// them at the beginning of list
// 'newHead'
while (current != null && count < k)
{
next = current.next;
newHead = push(newHead, current);
current = next;
count++;
}
// if next group exists then making the desired
// adjustments in the link
if (next != null)
{
head.next = revListInGroupOfGivenSize(next, k);
head.next.prev = head;
}
// pointer to the new head of the
// reversed group
return newHead;
}
// Function to print nodes in a
// given doubly linked list
static void printList(Node head)
{
while (head != null)
{
Console.Write(head.data + " ");
head = head.next;
}
}
// Driver code
public static void Main(String []args)
{
// Start with the empty list
Node head = null;
// Create doubly linked: 10<->8<->4<->2
head = push(head, getNode(2));
head = push(head, getNode(4));
head = push(head, getNode(8));
head = push(head, getNode(10));
int k = 2;
Console.Write("Original list: ");
printList(head);
// Reverse doubly linked list in groups of
// size 'k'
head = revListInGroupOfGivenSize(head, k);
Console.Write("\nModified list: ");
printList(head);
}
}
// This code is contributed by Arnab Kundu
Javascript
<script>
// javascript implementation to reverse a doubly linked list
// in groups of given size
// Represents a node of doubly linked list
class Node {
constructor() {
this.data = 0;
this.prev = null;
this.next = null;
}
}
// function to get a new node
function getNode(data) {
// allocating node
var new_node = new Node();
new_node.data = data;
new_node.next = new_node.prev = null;
return new_node;
}
// function to insert a node at the beginning
// of the Doubly Linked List
function push(head, new_node) {
// since we are adding at the beginning,
// prev is always NULL
new_node.prev = null;
// link the old list off the new node
new_node.next = head;
// 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;
return head;
}
// function to reverse a doubly linked list
// in groups of given size
function revListInGroupOfGivenSize(head , k) {
var current = head;
var next = null;
var newHead = null;
var count = 0;
// reversing the current group of k
// or less than k nodes by adding
// them at the beginning of list
// 'newHead'
while (current != null && count < k) {
next = current.next;
newHead = push(newHead, current);
current = next;
count++;
}
// if next group exists then making the desired
// adjustments in the link
if (next != null) {
head.next = revListInGroupOfGivenSize(next, k);
head.next.prev = head;
}
// pointer to the new head of the
// reversed group
return newHead;
}
// Function to print nodes in a
// given doubly linked list
function printList(head) {
while (head != null) {
document.write(head.data + " ");
head = head.next;
}
}
// Driver code
// Start with the empty list
var head = null;
// Create doubly linked: 10<->8<->4<->2
head = push(head, getNode(2));
head = push(head, getNode(4));
head = push(head, getNode(8));
head = push(head, getNode(10));
var k = 2;
document.write("Original list: ");
printList(head);
// Reverse doubly linked list in groups of
// size 'k'
head = revListInGroupOfGivenSize(head, k);
document.write("<br/>Modified list: ");
printList(head);
// This code contributed by aashish1995
</script>
Producción
Original list: 10 8 4 2 Modified list: 8 10 2 4
Complejidad temporal: O(n).
Podemos simplificar aún más la implementación de este algoritmo usando la misma idea con recursividad en una sola función.
C++
#include <iostream>
using namespace std;
struct Node {
int data;
Node *next, *prev;
};
// function to add Node at the end of a Doubly LinkedList
Node* insertAtEnd(Node* head, int data)
{
Node* new_node = new Node();
new_node->data = data;
new_node->next = NULL;
Node* temp = head;
if (head == NULL) {
new_node->prev = NULL;
head = new_node;
return head;
}
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = new_node;
new_node->prev = temp;
return head;
}
// function to print Doubly LinkedList
void printDLL(Node* head)
{
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
// function to Reverse a doubly linked list
// in groups of given size
Node* reverseByN(Node* head, int k)
{
if (!head)
return NULL;
head->prev = NULL;
Node *temp, *curr = head, *newHead;
int count = 0;
while (curr != NULL && count < k) {
newHead = curr;
temp = curr->prev;
curr->prev = curr->next;
curr->next = temp;
curr = curr->prev;
count++;
}
// checking if the reversed LinkedList size is
// equal to K or not
// if it is not equal to k that means we have reversed
// the last set of size K and we don't need to call the
// recursive function
if (count >= k) {
Node* rest = reverseByN(curr, k);
head->next = rest;
if (rest != NULL)
// it is required for prev link otherwise u wont
// be backtrack list due to broken links
rest->prev = head;
}
return newHead;
}
int main()
{
Node* head;
for (int i = 1; i <= 10; i++) {
head = insertAtEnd(head, i);
}
printDLL(head);
int n = 4;
head = reverseByN(head, n);
printDLL(head);
}
Java
import java.io.*;
class Node {
int data;
Node next, prev;
}
class GFG {
// Function to add Node at the end of a
// Doubly LinkedList
static Node insertAtEnd(Node head, int data)
{
Node new_node = new Node();
new_node.data = data;
new_node.next = null;
Node temp = head;
if (head == null) {
new_node.prev = null;
head = new_node;
return head;
}
while (temp.next != null) {
temp = temp.next;
}
temp.next = new_node;
new_node.prev = temp;
return head;
}
// Function to print Doubly LinkedList
static void printDLL(Node head)
{
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
System.out.println();
}
// Function to Reverse a doubly linked list
// in groups of given size
static Node reverseByN(Node head, int k)
{
if (head == null)
return null;
head.prev = null;
Node temp;
Node curr = head;
Node newHead = null;
int count = 0;
while (curr != null && count < k) {
newHead = curr;
temp = curr.prev;
curr.prev = curr.next;
curr.next = temp;
curr = curr.prev;
count++;
}
// Checking if the reversed LinkedList size is
// equal to K or not. If it is not equal to k
// that means we have reversed the last set of
// size K and we don't need to call the
// recursive function
if (count >= k) {
Node rest = reverseByN(curr, k);
head.next = rest;
if (rest != null)
// it is required for prev link otherwise u
// wont be backtrack list due to broken
// links
rest.prev = head;
}
return newHead;
}
// Driver code
public static void main(String[] args)
{
Node head = null;
for (int i = 1; i <= 10; i++) {
head = insertAtEnd(head, i);
}
printDLL(head);
int n = 4;
head = reverseByN(head, n);
printDLL(head);
}
}
// This code is contributed by avanitrachhadiya2155
Python3
class Node: def __init__(self): self.data = 0; self.next = None; self.next = None; # Function to add Node at the end of a # Doubly LinkedList def insertAtEnd(head, data): new_Node = Node(); new_Node.data = data; new_Node.next = None; temp = head; if (head == None): new_Node.prev = None; head = new_Node; return head; while (temp.next != None): temp = temp.next; temp.next = new_Node; new_Node.prev = temp; return head; # Function to prDoubly LinkedList def printDLL(head): while (head != None): print(head.data, end=" "); head = head.next; print(); # Function to Reverse a doubly linked list # in groups of given size def reverseByN(head, k): if (head == None): return None; head.prev = None; temp=None; curr = head; newHead = None; count = 0; while (curr != None and count < k): newHead = curr; temp = curr.prev; curr.prev = curr.next; curr.next = temp; curr = curr.prev; count += 1; # Checking if the reversed LinkedList size is # equal to K or not. If it is not equal to k # that means we have reversed the last set of # size K and we don't need to call the # recursive function if (count >= k): rest = reverseByN(curr, k); head.next = rest; if (rest != None): # it is required for prev link otherwise u # wont be backtrack list due to broken # links rest.prev = head; return newHead; # Driver code if __name__ == '__main__': head = None; for i in range(1,11): head = insertAtEnd(head, i); printDLL(head); n = 4; head = reverseByN(head, n); printDLL(head); # This code contributed by umadevi9616
C#
using System;
using System.Collections.Generic;
public class GFG {
public class Node {
public int data;
public Node next, prev;
}
// Function to add Node at the end of a
// Doubly List
static Node insertAtEnd(Node head, int data)
{
Node new_node = new Node();
new_node.data = data;
new_node.next = null;
Node temp = head;
if (head == null) {
new_node.prev = null;
head = new_node;
return head;
}
while (temp.next != null) {
temp = temp.next;
}
temp.next = new_node;
new_node.prev = temp;
return head;
}
// Function to print Doubly List
static void printDLL(Node head)
{
while (head != null) {
Console.Write(head.data + " ");
head = head.next;
}
Console.WriteLine();
}
// Function to Reverse a doubly linked list
// in groups of given size
static Node reverseByN(Node head, int k)
{
if (head == null)
return null;
head.prev = null;
Node temp;
Node curr = head;
Node newHead = null;
int count = 0;
while (curr != null && count < k) {
newHead = curr;
temp = curr.prev;
curr.prev = curr.next;
curr.next = temp;
curr = curr.prev;
count++;
}
// Checking if the reversed List size is
// equal to K or not. If it is not equal to k
// that means we have reversed the last set of
// size K and we don't need to call the
// recursive function
if (count >= k) {
Node rest = reverseByN(curr, k);
head.next = rest;
if (rest != null)
// it is required for prev link otherwise u
// wont be backtrack list due to broken
// links
rest.prev = head;
}
return newHead;
}
// Driver code
public static void Main(String[] args)
{
Node head = null;
for (int i = 1; i <= 10; i++) {
head = insertAtEnd(head, i);
}
printDLL(head);
int n = 4;
head = reverseByN(head, n);
printDLL(head);
}
}
// This code is contributed by umadevi9616
Javascript
<script>
class Node {
constructor()
{
this.data = 0;
this.next = null;
this.prev = null;
}
};
// function to add Node at the end of a Doubly LinkedList
function insertAtEnd(head, data)
{
var new_node = new Node();
new_node.data = data;
new_node.next = null;
var temp = head;
if (head == null) {
new_node.prev = null;
head = new_node;
return head;
}
while (temp.next != null) {
temp = temp.next;
}
temp.next = new_node;
new_node.prev = temp;
return head;
}
// function to print Doubly LinkedList
function printDLL(head)
{
while (head != null) {
document.write( head.data + " ");
head = head.next;
}
document.write("<br>");
}
// function to Reverse a doubly linked list
// in groups of given size
function reverseByN(head, k)
{
if (!head)
return null;
head.prev = null;
var temp, curr = head, newHead;
var count = 0;
while (curr != null && count < k) {
newHead = curr;
temp = curr.prev;
curr.prev = curr.next;
curr.next = temp;
curr = curr.prev;
count++;
}
// checking if the reversed LinkedList size is
// equal to K or not
// if it is not equal to k that means we have reversed
// the last set of size K and we don't need to call the
// recursive function
if (count >= k) {
var rest = reverseByN(curr, k)
head.next = rest;
if(rest != null)
/it is required for prev link otherwise u wont be backtrack list due to broken links
rest.prev = head;
}
return newHead;
}
var head;
for (var i = 1; i <= 10; i++) {
head = insertAtEnd(head, i);
}
printDLL(head);
var n = 4;
head = reverseByN(head, n);
printDLL(head);
</script>
Producción
1 2 3 4 5 6 7 8 9 10 4 3 2 1 8 7 6 5 10 9
Otro enfoque (Método iterativo): aquí usaremos el método iterativo en el que comenzaremos desde el Node principal e invertiremos los Nodes k en el grupo. Después de invertir los k Nodes, continuaremos este proceso con el siguiente Node después del k hasta que se vuelva nulo. Lograremos el resultado deseado en un solo paso de la lista enlazada con la complejidad de tiempo de O(n) y la complejidad de espacio de O(1).
C++
// C++ implementation to reverse a doubly linked list
// in groups of given size without recursion
// Iterative Method
#include <iostream>
using namespace std;
// Represents a node of doubly linked list
struct Node {
int data;
Node *next, *prev;
};
// function to get a new node
Node* getNode(int data)
{
// allocating node
Node* new_node = new Node();
new_node->data = data;
new_node->next = new_node->prev = NULL;
return new_node;
}
// function to insert a node at the beginning
// of the Doubly Linked List
Node* push(Node* head, Node* new_node)
{
// since we are adding at the beginning,
// prev is always NULL
new_node->prev = NULL;
// link the old list off the new node
new_node->next = head;
// 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;
return head;
}
// function to reverse a doubly linked list
// in groups of given size
Node* revListInGroupOfGivenSize(Node* head, int k)
{
if (!head)
return head;
Node* st = head;
Node* globprev = NULL;
Node* ans = NULL;
while (st) {
int count = 1; // to count k nodes
Node* curr = st;
Node* prev = NULL;
Node* next = NULL;
while (curr && count <= k) { // reversing k nodes
next = curr->next;
curr->prev = next;
curr->next = prev;
prev = curr;
curr = next;
count++;
}
if (!ans) {
ans = prev; // to store ans i.e the new head
ans->prev = NULL;
}
if (!globprev)
globprev = st; // assigning the last node of the
// reversed k nodes
else {
globprev->next = prev;
prev->prev
= globprev; // connecting last node of last
// k group to the first node of
// present k group
globprev = st;
}
st = curr; // advancing the pointer for the next k
// group
}
return ans;
}
// Function to print nodes in a
// given doubly linked list
void printList(Node* head)
{
while (head) {
cout << head->data << " ";
head = head->next;
}
}
// Driver code
int main()
{
// Start with the empty list
Node* head = NULL;
// Create doubly linked: 10<->8<->4<->2
head = push(head, getNode(2));
head = push(head, getNode(4));
head = push(head, getNode(8));
head = push(head, getNode(10));
int k = 2;
cout << "Original list: ";
printList(head);
// Reverse doubly linked list in groups of
// size 'k'
head = revListInGroupOfGivenSize(head, k);
cout << "\nModified list: ";
printList(head);
return 0;
}
// This code is contributed by Tapesh (tapeshdua420)
Java
// Java implementation to reverse a doubly linked list
// in groups of given size without recursion
// Iterative Method
import java.io.*;
import java.util.*;
// Represents a node of doubly linked list
class Node {
int data;
Node next, prev;
}
class GFG {
// function to get a new node
static Node getNode(int data)
{
// allocating node
Node new_node = new Node();
new_node.data = data;
new_node.next = new_node.prev = null;
return new_node;
}
// function to insert a node at the beginning
// of the Doubly Linked List
static Node push(Node head, Node new_node)
{
// since we are adding at the beginning,
// prev is always NULL
new_node.prev = null;
// link the old list off the new node
new_node.next = head;
// 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;
return head;
}
// function to reverse a doubly linked list
// in groups of given size
static Node revListInGroupOfGivenSize(Node head, int k)
{
if (head == null)
return head;
Node st = head;
Node globprev = null;
Node ans = null;
while (st != null) {
int count = 1; // to count k nodes
Node curr = st;
Node prev = null;
Node next = null;
while (curr != null
&& count <= k) { // reversing k nodes
next = curr.next;
curr.prev = next;
curr.next = prev;
prev = curr;
curr = next;
count++;
}
if (ans == null) {
ans = prev; // to store ans i.e the new head
ans.prev = null;
}
if (globprev == null) {
globprev = st; // assigning the last node of
// the reversed k nodes
}
else {
globprev.next = prev;
prev.prev
= globprev; // connecting last node of
// last k group to the first
// node of present k group
globprev = st;
}
st = curr; // advancing the pointer for the next
// k group
}
return ans;
}
// Function to print nodes in a
// given doubly linked list
static void printList(Node head)
{
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
}
// Driver code
public static void main(String args[])
{
// Start with the empty list
Node head = null;
// Create doubly linked: 10<->8<->4<->2
head = push(head, getNode(2));
head = push(head, getNode(4));
head = push(head, getNode(8));
head = push(head, getNode(10));
int k = 2;
System.out.print("Original list: ");
printList(head);
// Reverse doubly linked list in groups of
// size 'k'
head = revListInGroupOfGivenSize(head, k);
System.out.print("\nModified list: ");
printList(head);
}
}
// This code is contributed by Chayan Sharma
Python3
# Python implementation to reverse a doubly
# linked list in groups of given size without recursion
# Iterative method.
# Represents a node of doubly linked list.
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to get a new Node.
def getNode(data):
# allocating node
new_node = Node(0)
new_node.data = data
new_node.next = new_node.prev = None
return new_node
# Function to insert a node at the beginning of the doubly linked list.
def push(head, new_node):
# since we are adding at the beginning, prev is always null.
new_node.prev = None
# link the old list off the new node.
new_node.next = head
# change prev of head node to new node.
if ((head) != None):
head.prev = new_node
# move the head to point to the new node.
head = new_node
return head
# Function to print nodes in given doubly linked list.
def printList(head):
while (head):
print(head.data, end=" ")
head = head.next
# Function to reverse a doubly linked list in groups of given size.
def revListInGroupOfGivenSize(head, k):
if head is None:
return head
st = head
globprev, ans = None, None
while (st != None):
# Count the number of nodes.
count = 1
curr = st
prev, next_node = None, None
while (curr != None and count <= k):
# Reversing k nodes.
next_node = curr.next
curr.prev = next_node
curr.next = prev
prev = curr
curr = next_node
count += 1
if ans is None:
ans = prev
ans.prev = None
if globprev is None:
globprev = st
else:
globprev.next = prev
prev.prev = globprev
globprev = st
st = curr
return ans
# Start with the empty list.
head = None
# Create a doubly linked list: 10<->8<->4<->2
head = push(head, getNode(2))
head = push(head, getNode(4))
head = push(head, getNode(8))
head = push(head, getNode(10))
print("Original list:", end=" ")
printList(head)
k = 2
# Reverse doubly linked list in groups of size 'k'
head = revListInGroupOfGivenSize(head, k)
print("\nModified list:", end=" ")
printList(head)
# This code is contributed by lokesh (lokeshmvs21).
C#
// C# implementation to reverse a doubly linked list in
// groups of given size without recursion Iterative Method
using System;
// Represents a node of doubly linked list
public class Node {
public int data;
public Node next, prev;
}
public class GFG {
// Function to get a new Node.
static Node getNode(int data)
{
// allocating a new node.
Node new_node = new Node();
new_node.data = data;
new_node.next = new_node.prev = null;
return new_node;
}
// Function to insert a node at the beginning of the
// doubly linked list.
static Node push(Node head, Node new_node)
{
// since we are adding at the beginning, prev is
// always null.
new_node.prev = null;
// link the old list off the new node.
new_node.next = head;
// 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;
return head;
}
// Function to print nodes in a given doubly linked
// list.
static void printList(Node head)
{
while (head != null) {
Console.Write(head.data + " ");
head = head.next;
}
}
// Function to reverse a doubly linked list in groups of
// given size
static Node revListInGroupOfGivenSize(Node head, int k)
{
if (head == null) {
return head;
}
Node st = head;
Node globprev = null;
Node ans = null;
while (st != null) {
// count the number of nodes.
int count = 1;
Node curr = st;
Node prev = null;
Node next = null;
// reversing k nodes.
while (curr != null && count <= k) {
next = curr.next;
curr.prev = next;
curr.next = prev;
prev = curr;
curr = next;
count++;
}
if (ans == null) {
// to store ans i.e the new head
ans = prev;
ans.prev = null;
}
if (globprev == null) {
// assigning the last node of the reveresd k
// nodes.
globprev = st;
}
else {
globprev.next = prev;
prev.prev = globprev;
// connecting last node of last k group to
// the first node of present k group
globprev = st;
}
// advancing the pointer for the next k group
st = curr;
}
return ans;
}
static public void Main()
{
// Start with the empty list.
Node head = null;
// Create doubly linked list : 10<->8<->4<->2
head = push(head, getNode(2));
head = push(head, getNode(4));
head = push(head, getNode(8));
head = push(head, getNode(10));
Console.Write("Original list: ");
printList(head);
int k = 2;
// Reverse doubly linked list in groups of size 'k'
head = revListInGroupOfGivenSize(head, k);
Console.Write("\nModified list: ");
printList(head);
}
}
// This code is contributed by lokesh (lokeshmvs21)
Javascript
<script>
// Javascript implementation to reverse a doubly linked list
// in groups of given size without recursion
// Iterative Method
// Represents a node of doubly linked list
class Node {
constructor() {
this.data = null;
this.next = null;
this.prev = null;
}
}
// function to get a new node
function getNode(data) {
// allocating node
let new_node = new Node();
new_node.data = data;
new_node.next = new_node.prev = null;
return new_node;
}
// function to insert a node at the beginning
// of the Doubly Linked List
function push(head, new_node) {
// since we are adding at the beginning,
// prev is always NULL
new_node.prev = null;
// link the old list off the new node
new_node.next = head;
// 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;
return head;
}
// function to reverse a doubly linked list
// in groups of given size
function revListInGroupOfGivenSize(head, k) {
if (head == null)
return head;
let st = head;
let globprev = null;
let ans = null;
while (st != null) {
let count = 1; // to count k nodes
let curr = st;
let prev = null;
let next = null;
while (curr != null
&& count <= k) { // reversing k nodes
next = curr.next;
curr.prev = next;
curr.next = prev;
prev = curr;
curr = next;
count++;
}
if (ans == null) {
ans = prev; // to store ans i.e the new head
ans.prev = null;
}
if (globprev == null) {
globprev = st; // assigning the last node of
// the reversed k nodes
}
else {
globprev.next = prev;
prev.prev
= globprev; // connecting last node of
// last k group to the first
// node of present k group
globprev = st;
}
st = curr; // advancing the pointer for the next
// k group
}
return ans;
}
// Function to print nodes in a
// given doubly linked list
function printList(head) {
while (head != null) {
document.write(head.data + " ");
head = head.next;
}
}
// Driver code
// Start with the empty list
let head = null;
// Create doubly linked: 10<->8<->4<->2
head = push(head, getNode(2));
head = push(head, getNode(4));
head = push(head, getNode(8));
head = push(head, getNode(10));
let k = 2;
document.write("Original list: ");
printList(head);
// Reverse doubly linked list in groups of
// size 'k'
head = revListInGroupOfGivenSize(head, k);
document.write("<br>Modified list: ");
printList(head);
// This code is contributed by Saurabh Jaiswal
</script>
Producción
Original list: 10 8 4 2 Modified list: 8 10 2 4
Complejidad de tiempo: O(n), donde n es el número de Nodes en la lista original
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ayushjauhari14 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA