Reverse a doubly linked list in groups of given size
Last Updated :
20 Jan, 2023
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 groups 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 a 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++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *next, *prev;
};
Node* getNode(int data)
{
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->data = data;
new_node->next = new_node->prev = NULL;
return new_node;
}
void push(Node** head_ref, Node* new_node)
{
new_node->prev = NULL;
new_node->next = (*head_ref);
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
(*head_ref) = new_node;
}
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;
push(&newHead, current);
current = next;
count++;
}
if (next != NULL)
{
head->next = revListInGroupOfGivenSize(next, k);
head->next->prev = head;
}
newHead->prev = NULL;
return newHead;
}
void printList(Node* head)
{
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
}
int main()
{
Node* head = NULL;
push(&head, getNode(2));
push(&head, getNode(4));
push(&head, getNode(8));
push(&head, getNode(10));
int k = 2;
cout << "Original list: ";
printList(head);
head = revListInGroupOfGivenSize(head, k);
cout << "\nModified list: ";
printList(head);
return 0;
}
|
Java
import java.io.*;
import java.util.*;
class Node
{
int data;
Node next, prev;
}
class GFG
{
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;
}
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 printList(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: ");
printList(head);
head = revListInGroupOfGivenSize(head, k);
System.out.print("\nModified list: ");
printList(head);
}
}
|
Python3
class Node:
def __init__(self, data):
self.data = data
self.next = next
def getNode(data):
new_node = Node(0)
new_node.data = data
new_node.next = new_node.prev = None
return new_node
def push(head_ref, new_node):
new_node.prev = None
new_node.next = (head_ref)
if ((head_ref) != None):
(head_ref).prev = new_node
(head_ref) = new_node
return head_ref
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
def printList(head):
while (head != None):
print( head.data , end=" ")
head = head.next
head = None
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)
head = revListInGroupOfGivenSize(head, k)
print("\nModified list: ")
printList(head)
|
C#
using System;
public class Node
{
public int data;
public Node next, prev;
}
class GFG
{
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;
}
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 printList(Node head)
{
while (head != null)
{
Console.Write(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;
Console.Write("Original list: ");
printList(head);
head = revListInGroupOfGivenSize(head, k);
Console.Write("\nModified list: ");
printList(head);
}
}
|
Javascript
<script>
class Node {
constructor() {
this.data = 0;
this.prev = null;
this.next = null;
}
}
function getNode(data) {
var new_node = new Node();
new_node.data = data;
new_node.next = new_node.prev = null;
return new_node;
}
function push(head, new_node) {
new_node.prev = null;
new_node.next = head;
if (head != null)
head.prev = new_node;
head = new_node;
return head;
}
function revListInGroupOfGivenSize(head , k) {
var current = head;
var next = null;
var newHead = null;
var 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;
}
function printList(head) {
while (head != null) {
document.write(head.data + " ");
head = head.next;
}
}
var head = null;
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);
head = revListInGroupOfGivenSize(head, k);
document.write("<br/>Modified list: ");
printList(head);
</script>
|
Output
Original list: 10 8 4 2
Modified list: 8 10 2 4
Time complexity: O(n), because we are looping through the entire list of n nodes to reverse the list in groups of given size.
Auxiliary Space: O(1), because we are not using any extra space. We are just using the existing nodes and the variables to reverse the list.
We can further simplify the implementation of this algorithm using the same idea with recursion in just one function.
C++
#include <iostream>
using namespace std;
struct Node {
int data;
Node *next, *prev;
};
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;
}
void printDLL(Node* head)
{
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
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++;
}
if (count >= k) {
Node* rest = reverseByN(curr, k);
head->next = rest;
if (rest != NULL)
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 {
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;
}
static void printDLL(Node head)
{
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
System.out.println();
}
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++;
}
if (count >= k) {
Node rest = reverseByN(curr, k);
head.next = rest;
if (rest != null)
rest.prev = head;
}
return newHead;
}
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);
}
}
|
Python3
class Node:
def __init__(self):
self.data = 0;
self.next = None;
self.next = None;
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;
def printDLL(head):
while (head != None):
print(head.data, end=" ");
head = head.next;
print();
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;
if (count >= k):
rest = reverseByN(curr, k);
head.next = rest;
if (rest != None):
rest.prev = head;
return newHead;
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);
|
C#
using System;
using System.Collections.Generic;
public class GFG {
public class Node {
public int data;
public Node next, prev;
}
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;
}
static void printDLL(Node head)
{
while (head != null) {
Console.Write(head.data + " ");
head = head.next;
}
Console.WriteLine();
}
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++;
}
if (count >= k) {
Node rest = reverseByN(curr, k);
head.next = rest;
if (rest != null)
rest.prev = head;
}
return newHead;
}
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);
}
}
|
Javascript
<script>
class Node {
constructor()
{
this.data = 0;
this.next = null;
this.prev = null;
}
};
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 printDLL(head)
{
while (head != null) {
document.write( head.data + " ");
head = head.next;
}
document.write("<br>");
}
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++;
}
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>
|
Output
1 2 3 4 5 6 7 8 9 10
4 3 2 1 8 7 6 5 10 9
Time complexity: O(n), because we are looping through the entire list of n nodes to reverse the list in groups of given size.
Auxiliary Space: O(1), if we consider recursive call stack then it will be O(K)
Another approach (Iterative Method) : Here we will be using the iterative method in which we will begin from head node and reverse k nodes in the group. After reversing the k nodes we will continue this process with the next node after the k node until it becomes null. We will the achieving the desired result in only a single pass of the linked list with the time complexity of O(n) and space complexity of O(1).
C++
#include <iostream>
using namespace std;
struct Node {
int data;
Node *next, *prev;
};
Node* getNode(int data)
{
Node* new_node = new Node();
new_node->data = data;
new_node->next = new_node->prev = NULL;
return new_node;
}
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;
}
Node* revListInGroupOfGivenSize(Node* head, int k)
{
if (!head)
return head;
Node* st = head;
Node* globprev = NULL;
Node* ans = NULL;
while (st) {
int count = 1;
Node* curr = st;
Node* prev = NULL;
Node* next = NULL;
while (curr && count <= k) {
next = curr->next;
curr->prev = next;
curr->next = prev;
prev = curr;
curr = next;
count++;
}
if (!ans) {
ans = prev;
ans->prev = NULL;
}
if (!globprev)
globprev = st;
else {
globprev->next = prev;
prev->prev
= globprev;
globprev = st;
}
st = curr;
}
return ans;
}
void printList(Node* head)
{
while (head) {
cout << head->data << " ";
head = head->next;
}
}
int main()
{
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;
cout << "Original list: ";
printList(head);
head = revListInGroupOfGivenSize(head, k);
cout << "\nModified list: ";
printList(head);
return 0;
}
|
Java
import java.io.*;
import java.util.*;
class Node {
int data;
Node next, prev;
}
class GFG {
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;
}
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;
Node curr = st;
Node prev = null;
Node next = null;
while (curr != null
&& count <= k) {
next = curr.next;
curr.prev = next;
curr.next = prev;
prev = curr;
curr = next;
count++;
}
if (ans == null) {
ans = prev;
ans.prev = null;
}
if (globprev == null) {
globprev = st;
}
else {
globprev.next = prev;
prev.prev
= globprev;
globprev = st;
}
st = curr;
}
return ans;
}
static void printList(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: ");
printList(head);
head = revListInGroupOfGivenSize(head, k);
System.out.print("\nModified list: ");
printList(head);
}
}
|
Python3
class Node:
def __init__(self, data):
self.data = data
self.next = None
def getNode(data):
new_node = Node(0)
new_node.data = data
new_node.next = new_node.prev = None
return new_node
def push(head, new_node):
new_node.prev = None
new_node.next = head
if ((head) != None):
head.prev = new_node
head = new_node
return head
def printList(head):
while (head):
print(head.data, end=" ")
head = head.next
def revListInGroupOfGivenSize(head, k):
if head is None:
return head
st = head
globprev, ans = None, None
while (st != None):
count = 1
curr = st
prev, next_node = None, None
while (curr != None and count <= k):
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
head = None
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
head = revListInGroupOfGivenSize(head, k)
print("\nModified list:", end=" ")
printList(head)
|
C#
using System;
public class Node {
public int data;
public Node next, prev;
}
public class GFG {
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;
}
static void printList(Node head)
{
while (head != null) {
Console.Write(head.data + " ");
head = head.next;
}
}
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;
Node curr = st;
Node prev = null;
Node next = null;
while (curr != null && count <= k) {
next = curr.next;
curr.prev = next;
curr.next = prev;
prev = curr;
curr = next;
count++;
}
if (ans == null) {
ans = prev;
ans.prev = null;
}
if (globprev == null) {
globprev = st;
}
else {
globprev.next = prev;
prev.prev = globprev;
globprev = st;
}
st = curr;
}
return ans;
}
static public void Main()
{
Node head = null;
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;
head = revListInGroupOfGivenSize(head, k);
Console.Write("\nModified list: ");
printList(head);
}
}
|
Javascript
<script>
class Node {
constructor() {
this.data = null;
this.next = null;
this.prev = null;
}
}
function getNode(data) {
let new_node = new Node();
new_node.data = data;
new_node.next = new_node.prev = null;
return new_node;
}
function push(head, new_node) {
new_node.prev = null;
new_node.next = head;
if (head != null)
head.prev = new_node;
head = new_node;
return head;
}
function revListInGroupOfGivenSize(head, k) {
if (head == null)
return head;
let st = head;
let globprev = null;
let ans = null;
while (st != null) {
let count = 1;
let curr = st;
let prev = null;
let next = null;
while (curr != null
&& count <= k) {
next = curr.next;
curr.prev = next;
curr.next = prev;
prev = curr;
curr = next;
count++;
}
if (ans == null) {
ans = prev;
ans.prev = null;
}
if (globprev == null) {
globprev = st;
}
else {
globprev.next = prev;
prev.prev
= globprev;
globprev = st;
}
st = curr;
}
return ans;
}
function printList(head) {
while (head != null) {
document.write(head.data + " ");
head = head.next;
}
}
let head = null;
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);
head = revListInGroupOfGivenSize(head, k);
document.write("<br>Modified list: ");
printList(head);
</script>
|
Output
Original list: 10 8 4 2
Modified list: 8 10 2 4
Time Complexity: O(n), where n is the number of nodes in the original list
Auxiliary Space: O(1)
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...