Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach 1- Creating a New List
3.1.
Program
3.2.
Complexities
4.
Approach 2- Updating the Existing List
4.1.
Program
4.2.
Complexities
5.
Frequently Asked Questions
5.1.
How is a Doubly Linked List different than a Singly Linked List?
5.2.
What is the time complexity for reversing a singly linked list?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Reverse a Doubly-Linked List in Given Size

Linked List

Introduction

Joseph Weizenbaum designed SLIP, a list processing computer programming language, in the 1960s. SLIP or Symmetric List Processor used circular doubly linked lists data structure with fixed-size data fields internally.

A Doubly Linked List is one in which each node maintains not only the address to the next node but also the address to the previous node. 

Today we’ll be discussing a doubly linked list problem:  Reverse a Doubly-linked list in groups of size K.

So before further ado, let's get right into it.

Also see, Reverse a Linked Lists and Rabin Karp Algorithm

Problem Statement

You are given a doubly-Linked list with the start node 'HEAD' and an integer 'K'. You have to return a modified list which is reversed in the group of size 'K'.

Example

Illustration Image

Approach 1- Creating a New List

One way to reverse the list is to create a new list in which we loop through the groups of size 'K', and while looping, we'll insert the elements to the front of the new list. This way, we will reverse 'K' nodes. Next, we check if there are any groups left to reverse then we'll continue the same process again.

Let's define the algorithm in detail.

  • First, we initialize a pointer 'START' pointing to 'HEAD', and create a new node 'NEW_TAIL'. This will store the tail of the current reversed group.
  • Now we run the loop until either 'START' is NULL or we reach at the end of the group, and create a new node and insert it at the beginning of the new list.
  • After this, we have the 'NEW_HEAD' pointer that points to the start of the reversed group.
  • Once we've finished the traversal of the list, we'll return 'NEW_HEAD'. Else, we will compute the next reversed group and store it in  'NEW_TAIL'->next. Then return.

Program

#include <iostream>
using namespace std;

// Class for Linked List Node.
class Node
{
public:
   // Variable to store data of the node.
   int data;
   // Pointer to the next node.
   Node *next;
   // Pointer to the previous Node.
   Node *previous;
};

// Function to print the list.
void printLinkedList(Node *head)
{
   Node *temp = head;
   while (temp != NULL)
   {
       cout << temp->data << "  ";
       temp = temp->next;
   }
   cout << endl;
}

// Function to reverse a doubly-linked List in groups of size K.
Node *reverseDLLSectionOfGivenSize(Node *head, int k)
{
   Node *start = head;
   Node *newTail = new Node();
   Node *temp = newTail, *ptr;
   int x = k;
   
   // We'll loop through the group and insert the elements at the start of the new doubly-linked List.
   while (start != NULL && x--)
   {
       // Creating the new node and copying the data of the current node.
       ptr = new Node();
       ptr->data = start->data;
       
       // Next we insert this at the beginning of the new doubly-linked list.
       temp->previous = ptr;
       ptr->next = temp;
       
       // Updating the new head.
       temp = temp->previous;
       
       // Incrementing to the next node.
       start = start->next;
   }
   
   // We store the value of ‘NEW_HEAD’ now.
   Node *newHead = ptr;
   
   // And we have the ‘NEW_TAIL’ of the new List.
   newTail = newTail->previous;
   
   // If we've not finished the list. We recurse to reverse the next Group, and NEW_HEAD (next group) will be stored in the next of the NEW_TAIL.
   if (start != NULL)
   {
       newTail->next = reverseDLLSectionOfGivenSize(start, k);
   }
   
   // ELse we point the ‘NEW_TAIL’ next to ‘NULL’.
   else
   {
       newTail->next = NULL;
   }
   
   // Return the updated ‘HEAD’ node.
   return newHead;
}

int main()
{
   int n, x, k;
   cout << "Enter the number of elements in doubly-Linked List: ";
   cin >> n;
   Node *head = new Node();
   Node *temp = head;
   cout << " Enter the elements: ";
   // Creating the Doubly-linked list.
   for (int i = 0; i < n; i++)
   {
       cin >> x;
       Node *ptr = new Node();
       ptr->data = x;
       temp->next = ptr;
       ptr->previous = temp;
       temp = ptr;
   }
   
   head = head->next;
   cout << "Enter the group size K: ";
   cin >> k;
   
   // Printing the doubly-linked List before reversal.
   cout << "Before Reversal: ";
   printLinkedList(head);
   
   // Calling the function to reverse the doubly-linked list in groups of size K.
   Node *newHead = reverseDLLSectionOfGivenSize(head, k);
   
   // Printing the doubly-linked list after reversal.
   temp = newHead;
   cout << "After Reversal: ";
   printLinkedList(newHead);
   
   return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Input

Enter the number of elements in the doubly-linked List: 9
Enter the elements: 1 2 4 6 7 9 3 5 8
Enter the group size K: 3

Output

Before Reversal: 1 2 4 6 7 9 3 5 8
After Reversal: 4 2 1 9 7 6 8 5 3

Complexities

Time Complexity

O(N), where 'N' is the size of the doubly-linked list.

Since we are traversing the linked list once, the time complexity is O(N).

Space Complexity

O(N), where ‘N’ is the size of the doubly linked list.

Since we are creating a new doubly-linked list of size ‘N’.
Must Read  C Program to Reverse a Number

Approach 2- Updating the Existing List

We will try to reverse the doubly-linked list in a group of size 'K' in place in this approach. So what we'll do is to divide the linked list into groups and call reverseSection() function on each Group. This function will reverse the linked list by swapping node values starting from each end of the list.

Let’s see how the algorithm will look like.

  • First, we initialize the ‘START’ pointer pointing to the head of the node.
  • Now we loop until ‘START’ is not NULL and find the ‘END’ node of the current group.
  • Next, we call the reverseSection() function with the ‘START’ and ‘END’ of the group as parameters.
  • This function reverses this particular group.
  • And we repeat until we reach the end of the List.

Program

#include <iostream>
using namespace std;

// Class for Doubly-Linked List Node.
class Node
{
public:
   // Variable to store the data of the node.
   int data;
   // Pointer to the next Node.
   Node *next;
   // Pointer to the previous Node.
   Node *previous;
};

// Function to print the list.
void printLinkedList(Node *head)
{
   Node *temp = head;
   while (temp != NULL)
   {
       cout << temp->data << "  ";
       temp = temp->next;
   }
   cout << endl;
}

// Function to reverse the group between two nodes.
void reverseSection(Node *start, Node *end, int n)
{
   // We will continue from both ends until we reach the middle and keep swapping values.
   while (n-- && end != NULL && start != NULL)
   {
       // Swap values of 'START' and 'END' node.
       int temp = start->data;
       start->data = end->data;
       end->data = temp;
       
       // Increment 'START' pointer.
       start = start->next;
       
       // Decrement 'END' pointer.
       end = end->previous;
   }
}

// Function to reverse a doubly-linked list in groups of size K.
Node *reverseDLLSectionOfGivenSize(Node *head, int k)
{
   Node *start = head;
   
   // We'll loop until we reach the end of the List.
   while (start != NULL)
   {
       int x = k - 1;
       Node *end = start;
       
       // Now we find the last node of the current group.
       while (x-- && end->next != NULL)
       {
           end = end->next;
       }
       
       // Next, we store the last pointer.
       Node *prev = end;
       
       // Reverse this group.
       reverseSection(start, end, (k - x) / 2);
       
       // Update 'START' to the second group's 'START'.
       start = prev->next;
   }
   
   // Return the updated 'HEAD' node.
   return head;
}

int main()
{
   int n, x, k;
   cout << "Enter the number of elements in the doubly-linked list: ";
   cin >> n;
   Node *head = new Node();
   Node *temp = head;
   cout << " Enter the elements: ";
   
   // Creating Doubly-linked list.
   for (int i = 0; i < n; i++)
   {
       cin >> x;
       Node *ptr = new Node();
       ptr->data = x;
       temp->next = ptr;
       ptr->previous = temp;
       temp = ptr;
   }
   head = head->next;
   cout << "Enter the group size K: ";
   cin >> k;
   
   // Printing the doubly-linked list before reversal.
   cout << "Before Reversal: ";
   printLinkedList(head);
   
   // Calling function to reverse a doubly-linked list in groups of size K.
   Node *newHead = reverseDLLSectionOfGivenSize(head, k);
   
   // Printing the doubly-linked list after reversal.
   cout << "After Reversal: ";
   printLinkedList(newHead);
   
   return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Input

Enter the number of elements in the doubly-linked list: 6
Enter the elements: 1 2 4 6 7 9
Enter the group size K: 3

Output

Before Reversal: 1 2 4 6 7 9
After Reversal: 4 2 1 9 7 6

Complexities

Time Complexity

O(N), where 'N' is the size of the doubly-linked list.

We have, a number of groups = N/K. And for each group first, we traverse 'K' node to find the last node plus traverse the K / 2 node to swap values and reverse them. Hence total time for each group = K+K/2= 3/2.

Hence Time complexity = O((N / K) * (3 * K / 2))= O(3N/2) = O(N).

Space Complexity

O(1).

Since we are not using any extra auxiliary space.

Also read - Merge sort in linked list

Frequently Asked Questions

How is a Doubly Linked List different than a Singly Linked List?

The nodes of Doubly Linked Lists have pointers to their previous nodes as well as their next nodes in them. Whereas the nodes of a singly Linked List only have pointers to the next node.

What is the time complexity for reversing a singly linked list?

The time complexity for reversing a singly linked list is O(N) where N is the size of the linked list.

Conclusion

Handling pointers is a crucial skill for solving linked list problems. It's always a good idea to sketch down your pointer logic first before attempting to code it. You'll have a better knowledge of what you're doing this way. However, practice makes perfect, so keep solving more great problems. Many more exciting blogs can be found on Coding Ninjas Library. Please take a look at these.

Recommended Problems -

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Thanks for reading. I hope you are taking something valuable out of this blog. 

Live masterclass