Given a doubly linked list containing n nodes. The problem is to reverse every group of k nodes in the list.
Examples:
Prerequisite: Reverse a doubly linked list | Set-2.
Approach: Create a recursive function say reverse(head, k). This function receives the head or the first node of each group of k nodes. It reverses those group of k nodes by applying the approach discussed in Reverse a doubly linked list | Set-2. After reversing the group of k nodes the function checks whether next group of nodes exists in the list or not. If group exists then it makes a recursive call to itself with the first node of the next group and makes the necessary adjustments with the next and previous links of that group. Finally it returns the new head node of the reversed group.
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 beginging // of the Doubly Linked List void push(Node** head_ref, Node* new_node) { // since we are adding at the begining, // 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 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 << "
Modified 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("
Modified list: "); printList(head); } } // This code is contributed by rachana soma |
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("
Modified list: "); printList(head); } } // This code is contributed by Arnab Kundu |
Output:
Original list: 10 8 4 2 Modified list: 8 10 2 4
Time Complexity: O(n).
leave a comment
0 Comments