Reverse a doubly-linked list in groups of given size

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 
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<

						 

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.

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.

Previous post Merge Sort on a Singly Linked List
Next post LinkedList remove() Method in Java

Leave a Reply

Your email address will not be published. Required fields are marked *