Last Updated on March 9, 2022 by Ria Pathak
Introduction
One of the most crucial data structures to learn while preparing for interviews is the linked list. In a coding interview, having a thorough understanding of Linked Lists might be a major benefit.
Problem Statement
In this problem, we are given a Doubly Linked List and an integer X. We are asked to reverse the list in groups of size X.
Problem Statement Understanding
Let’s try to understand the problem statement with the help of examples.
If the given doubly linked list is: 5 1 6 2 7 10 and X = 3.
- According to the problem statement, we have been provided a doubly-linked list, and we need to reverse the list in groups of given size i.e. every group of nodes with the size X needs to be reversed.
- As we can see in the above given doubly linked list there are two groups 5 1 6 (from index 0 to 2) and 2 7 10 (from index 3 to 5) of size 3 which need to be reversed.
- So after reversing the group of nodes of size 3, our output resultant doubly linked list will be 6 1 5 10 7 2.
Let’s see another example.
If the given doubly linked list is: 5 1 6 2 7 and X = 3.
- As we can see in the above given doubly linked list 5 1 6 is a group of nodes of size 3 and 2 7 is a group of size 2. So, we need to reverse these two group of nodes.
- After reversing the above mentioned group of nodes, our resultant doubly linked list will be 6 1 5 7 2
Note: Suppose we were asked to reverse every group of nodes of size X in a doubly linked list. If in case there remains a group of nodes at the end of the linked list which has size smaller than X, then irrespective of its size we will reverse it in similar way as we were reversing nodes of group of size X.
Now I think from the above examples, the problem is clear. So let’s see how we can approach it.
Before moving to the approach section, try to think about how you can approach this problem.
- If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.
Let’s move to the approach section.
Approach
Our approach will be recursive:
- Here the main idea will be to use recursion to reverse the Doubly Linked List in group of given size, and after reversing a group, we need to call the function again for the next group of nodes if the next node is not null.
- The function will be called recursively until there are no elements left to be reversed.
- After the recursion is over, we will have our doubly linked list reversed in group of given size.
Algorithm
1) Our recursive function reverseListInGroupOfX() will receive the first node of every group of size X of the doubly linked list.
2) For every group of nodes in the recursive function reverseListInGroupOfX():
- First, we will reverse the nodes in the current group.
- After the nodes of the current group have been reversed, we will check whether the next group of nodes exists or not:
- If the next group of nodes exists, we will perform the same steps for the next group of nodes that we are performing for the current group.
- Also, for the current group of nodes, we need to link the next and the prev links of a group properly with the next group of nodes and previous group of nodes.
- Finally, we will return the new head of the group.
3) Following all these above steps until all the group of nodes have been reversed, we will get our resultant doubly linked list.
Dry Run
Code Implementation
#include<stdio.h>
#include<stdlib.h>
struct Node {
int data;
struct Node *next, *prev;
};
// function to get a new node
struct Node* getNode(int data)
{
// allocate space
struct Node* new_node = (struct Node*)malloc(sizeof(struct 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(struct Node** head_ref,struct 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
struct Node* revListInGroupOfGivenSize(struct Node* head, int k)
{
struct Node *current = head;
struct Node* next = NULL;
struct 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(struct Node* head)
{
while (head != NULL) {
printf("%d ",head->data);
head = head->next;
}
}
// Driver program to test above
int main()
{
// Start with the empty list
struct 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;
printf("Original list: ");
printList(head);
// Reverse doubly linked list in groups of
// size 'k'
head = revListInGroupOfGivenSize(head, k);
printf("\nModified list: ");
printList(head);
return 0;
}
#include <bits/stdc++.h>
using namespace std;
/* Structure of a doubly linked list node */
struct Node {
int data;
Node *next, *prev;
};
/* Creating and returning a new doubly linked list node */
Node* getNewNode(int data)
{
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->data = data;
new_node->next = new_node->prev = NULL;
return new_node;
}
/* Inserting a new node at head of doubly linked list */
void push(Node** newHead, Node* new_node)
{
new_node->prev = NULL;
new_node->next = (*newHead);
if ((*newHead) != NULL)
(*newHead)->prev = new_node;
(*newHead) = new_node;
}
/* Using this function we will be reversing doubly linked list in group of given size */
Node* reverseListInGroupOfX(Node* head, int X)
{
Node *current = head;
Node* next = NULL;
Node* newHead = NULL;
int count = 0;
while (current != NULL && count < X)
{
next = current->next;
push(&newHead, current);
current = next;
count++;
}
if (next != NULL)
{
head->next = reverseListInGroupOfX(next, X);
head->next->prev = head;
}
return newHead;
}
/* Using this function we will be printing the linked list content */
void printLinkedList(Node* head)
{
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
cout<<endl;
}
int main()
{
Node* head = NULL;
push(&head, getNewNode(10));
push(&head, getNewNode(7));
push(&head, getNewNode(2));
push(&head, getNewNode(6));
push(&head, getNewNode(1));
push(&head, getNewNode(5));
int X = 3;
cout<<"Initial doubly linked list"<<endl;
printLinkedList(head);
head = reverseListInGroupOfX(head, X);
cout<<"Doubly linked list after reversing in group of given size"<<endl;
printLinkedList(head);
return 0;
}
class Node
{
int data;
Node next, prev;
}
class ReverseGroups
{
static Node getNode(int data)
{
Node new_node = new Node();
new_node.data = data;
new_node.next = new_node.prev = null;
return new_node;
}
static Node push(Node head, Node new_node)
{
new_node.prev = null;
new_node.next = head;
if (head != null)
head.prev = new_node;
head = new_node;
return head;
}
// reversing doubly linked list in group of given size.
static Node revListInGroupOfGivenSize(Node head, int k)
{
Node current = head;
Node next = null;
Node newHead = null;
int count = 0;
while (current != null && count < k)
{
next = current.next;
newHead = push(newHead, current);
current = next;
count++;
}
if (next != null)
{
head.next = revListInGroupOfGivenSize(next, k);
head.next.prev = head;
}
return newHead;
}
static void printLinkedList(Node head)
{
while (head != null)
{
System.out.print(head.data + " ");
head = head.next;
}
}
public static void main(String args[])
{
Node head = null;
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: ");
printLinkedList(head);
head = revListInGroupOfGivenSize(head, k);
System.out.print("\nModified list in groups: ");
printLinkedList(head);
}
}
# Structure of a doubly linked list node
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
# Creating and returning a new doubly linked list node
def getNode(data):
new_node = Node(0)
new_node.data = data
new_node.next = new_node.prev = None
return new_node
# Inserting a new node at head of doubly linked list
def push(newHead, new_node):
new_node.prev = None
new_node.next = (newHead)
if ((newHead) != None):
(newHead).prev = new_node
(newHead) = new_node
return newHead
# Using this function we will be reversing doubly linked list in group of given size
def revListInGroupOfGivenSize( head, k):
current = head
next = None
newHead = None
count = 0
while (current != None and count < k):
next = current.next
newHead = push(newHead, current)
current = next
count = count + 1
if (next != None):
head.next = revListInGroupOfGivenSize(next, k)
head.next.prev = head
return newHead
# Using this function we will be printing the linked list content
def printList(head):
while (head != None):
print( head.data , end=" ")
head = head.next
head = None
head = push(head, getNode(10))
head = push(head, getNode(7))
head = push(head, getNode(2))
head = push(head, getNode(6))
head = push(head, getNode(1))
head = push(head, getNode(5))
k = 3
print("Initial doubly linked list")
printList(head)
head = revListInGroupOfGivenSize(head, k)
print("\nDoubly linked list after reversing in group of given size")
printList(head)
Output
Initial doubly linked list
5 1 6 2 7 10
Doubly linked list after reversing in group of given size
6 1 5 10 7 2
Time Complexity: O(n), as we need to traverse the list and traversing takes O(n) time.
[forminator_quiz id=”5116″]
So, In this blog, we have learned how you can reverse a Doubly Linked List in groups of a given size. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.