Given a doubly-linked list containing n nodes. The problem is to reverse every group of k nodes in the list.
Examples:
Input: List: 10<->8<->4<->2, K=2
Output: 8<->10<->2<->4Input: List: 1<->2<->3<->4<->5<->6<->7<->8, K=3
Output: 3<->2<->1<->6<->5<->4<->8<->7
Recursive Approach: The recursive approach to solving this problem is discussed in Set-1 of this article. Here, we are discussing the iterative approach.
Iterative Approach: This approach is a mix of two algorithms – reversing a doubly-linked list and reversing a linked list in a group of a given size. The function reverseK() individually reverses every k size linked list and connects them using prevFirst pointer that keeps track of the node that is bound to come after reversing. Follow the steps below to solve this problem:
- If N is less than equal to 1, then return head.
- Initialize the variables prevFirst as nullptr and curr as head.
- Initialize the variable firstPass as true.
- Traverse over a while loop till curr is not equal to null and perform the following tasks:
- Initialize the variable count as 0.
- Initialize the variables first as curr, next and prev as null.
- Traverse over a while loop till curr is not equal to null and count is less than K and perform the following tasks:
- Set the value of next as curr->next.
- If count equals 0 then set curr->next as null else curr->next as curr->prev.
- Set curr->prev as next, prev as curr and curr as next.
- Increase the value of count by 1.
- If firstPass is true then set head as next->prev and firstPass as false.
- Else, set prevFirst->next as prev.
- Set prevFirst as first.
- After performing the above steps, print the value of head as the answer.
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// A linked list nodeclass Node {public: int data; Node* next; Node* prev;};// Given a reference (pointer to pointer)// to the head of a list// and an int, inserts a new node on the// front of the list.void push(Node** head_ref, int new_data){ // Allocate node Node* new_node = new Node(); // Put in the data new_node->data = new_data; // Make next of new node as head // and previous as NULL new_node->next = (*head_ref); new_node->prev = NULL; // 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;}// Given a node as prev_node, insert// a new node after the given nodevoid insertAfter(Node* prev_node, int new_data){ // Check if the given prev_node is NULL if (prev_node == NULL) { cout << "the given previous " << "node cannot be NULL"; return; } // Allocate new node Node* new_node = new Node(); // Put in the data new_node->data = new_data; // Make next of new node as next of prev_node new_node->next = prev_node->next; // Make the next of prev_node as new_node prev_node->next = new_node; // Make prev_node as previous of new_node new_node->prev = prev_node; // Change previous of new_node's next node if (new_node->next != NULL) new_node->next->prev = new_node;}// Given a reference (pointer to pointer) to the head// of a DLL and an int, appends a new node at the endvoid append(Node** head_ref, int new_data){ // Allocate node Node* new_node = new Node(); Node* last = *head_ref; // Put in the data new_node->data = new_data; // This new node is going to be the last node, // so make next of it as NULL new_node->next = NULL; // If the Linked List is empty, // then make the new // node as head if (*head_ref == NULL) { new_node->prev = NULL; *head_ref = new_node; return; } // Else traverse till the last node while (last->next != NULL) last = last->next; // Change the next of last node last->next = new_node; // Make last node as previous of new node new_node->prev = last; return;}// This function prints contents of// linked list starting from the given nodevoid printList(Node* node){ Node* last; while (node != NULL) { cout << " " << node->data << " "; last = node; node = node->next; }}Node* reverseK(Node* head, int k){ // When head is NULL or linked list // has a single node we return if (head == NULL || head->next == NULL) return head; // PrevFirst pointer keeps track of // the node that is to be connected to each // reversed part. Node *prevFirst = NULL, *curr = head; // FirstPass variable is used so that we // can mark head of the new linkedlist. bool firstPass = true; while (curr != NULL) { int count = 0; // Next keeps track of the next node of curr // Prev keeps track of the previous node of curr Node *first = curr, *next = NULL, *prev = NULL; while (curr != NULL && count < k) { // Reversing the doubly linked list by just // swapping their next and prev pointers next = curr->next; if (count == 0) curr->next = NULL; else curr->next = curr->prev; curr->prev = next; prev = curr; curr = next; count++; } if (firstPass) { // Setting the head of the new linkedlist head = next->prev; firstPass = false; } else { prevFirst->next = prev; } prevFirst = first; } return head;}// Driver Codeint main(){ // Start with the empty list Node* head = NULL; // Insert 6. So linked list becomes 6->NULL append(&head, 6); // Insert 7 at the beginning. So // linked list becomes 7->6->NULL push(&head, 7); // Insert 1 at the beginning. So // linked list becomes 1->7->6->NULL push(&head, 1); // Insert 4 at the end. So linked // list becomes 1->7->6->4->NULL append(&head, 4); // Insert 8, after 7. So linked // list becomes 1->7->8->6->4->NULL insertAfter(head->next, 8); // list becomes 1->7->8->6->4->9->NULL append(&head, 9); head = reverseK(head, 2); printList(head); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// A linked list nodestatic class Node { int data; Node next; Node prev;};static Node head = null; // Given a reference (pointer to pointer)// to the head of a list// and an int, inserts a new node on the// front of the list.static void push(int new_data){ // Allocate node Node new_node = new Node(); // Put in the data new_node.data = new_data; // Make next of new node as head // and previous as null new_node.next = head; new_node.prev = null; // 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;}// Given a node as prev_node, insert// a new node after the given nodestatic void insertAfter(Node prev_node, int new_data){ // Check if the given prev_node is null if (prev_node == null) { System.out.print("the given previous " + "node cannot be null"); return; } // Allocate new node Node new_node = new Node(); // Put in the data new_node.data = new_data; // Make next of new node as next of prev_node new_node.next = prev_node.next; // Make the next of prev_node as new_node prev_node.next = new_node; // Make prev_node as previous of new_node new_node.prev = prev_node; // Change previous of new_node's next node if (new_node.next != null) new_node.next.prev = new_node;}// Given a reference (pointer to pointer) to the head// of a DLL and an int, appends a new node at the endstatic void append(int new_data){ // Allocate node Node new_node = new Node(); Node last = head; // Put in the data new_node.data = new_data; // This new node is going to be the last node, // so make next of it as null new_node.next = null; // If the Linked List is empty, // then make the new // node as head if (head == null) { new_node.prev = null; head = new_node; return; } // Else traverse till the last node while (last.next != null) last = last.next; // Change the next of last node last.next = new_node; // Make last node as previous of new node new_node.prev = last; return;}// This function prints contents of// linked list starting from the given nodestatic void printList(Node node){ Node last = new Node(); while (node != null) { System.out.print(" " + node.data+ " "); last = node; node = node.next; }}static Node reverseK(Node head, int k){ // When head is null or linked list // has a single node we return if (head == null || head.next == null) return head; // PrevFirst pointer keeps track of // the node that is to be connected to each // reversed part. Node prevFirst = null, curr = head; // FirstPass variable is used so that we // can mark head of the new linkedlist. boolean firstPass = true; while (curr != null) { int count = 0; // Next keeps track of the next node of curr // Prev keeps track of the previous node of curr Node first = curr, next = null, prev = null; while (curr != null && count < k) { // Reversing the doubly linked list by just // swapping their next and prev pointers next = curr.next; if (count == 0) curr.next = null; else curr.next = curr.prev; curr.prev = next; prev = curr; curr = next; count++; } if (firstPass) { // Setting the head of the new linkedlist head = next.prev; firstPass = false; } else { prevFirst.next = prev; } prevFirst = first; } return head;}// Driver Codepublic static void main(String[] args){ // Start with the empty list head = null; // Insert 6. So linked list becomes 6.null append( 6); // Insert 7 at the beginning. So // linked list becomes 7.6.null push(7); // Insert 1 at the beginning. So // linked list becomes 1.7.6.null push(1); // Insert 4 at the end. So linked // list becomes 1.7.6.4.null append( 4); // Insert 8, after 7. So linked // list becomes 1.7.8.6.4.null insertAfter(head.next, 8); // list becomes 1.7.8.6.4.9.null append( 9); head = reverseK(head, 2); printList(head);}}// This code contributed by shikhasingrajput |
Python3
# Python Code for the above problem.# Node classclass Node: # Function to initialise the node object def __init__(self, data): self.data = data # Assign data self.next = None # Initialize next as null self.prev = None # Initialize previous as null# Linked List class contains a Node objectclass LinkedList: # Function to initialize head def __init__(self): self.head = None # Function to insert a new node at the beginning def push(self, new_data): new_node = Node(new_data) new_node.next = self.head new_node.prev = None if self.head is not None: self.head.prev = new_node self.head = new_node # This function is in LinkedList class. Inserts a # new node after the given prev_node. def insertAfter(self, prev_node, new_data): if prev_node is None: return new_node = Node(new_data) new_node.next = prev_node.next prev_node.next = new_node new_node.prev = prev_node if new_node.next is not None: new_node.next.prev = new_node # This function is defined in Linked List class # Appends a new node at the end. def append(self, new_data): new_node = Node(new_data) last = self.head if self.head is None: new_node.prev = None self.head = new_node return while (last.next): last = last.next last.next = new_node new_node.prev = last # Utility function to print the linked list def printList(self): temp = self.head while(temp): print(temp.data, end=" ") temp = temp.next def reverseK(self, k): # When head is NULL or linked list # has a single node we return if self.head is None or self.head.next is None: return # PrevFirst pointer keeps track of # the node that is to be connected to each # reversed part. prevFirst, curr = None, self.head # FirstPass variable is used so that we # can mark head of the new linkedlist. firstPass = True while curr: count = 0 # Next keeps track of the next node of curr # Prev keeps track of the previous node of curr first, next_node, prev_node = curr, None, None while curr is not None and count < k: # Reversing the doubly linked list by just # swapping their next and prev pointers next_node = curr.next if count is 0: curr.next = None else: curr.next = curr.prev curr.prev = next_node prev_node = curr curr = next_node count += 1 if (firstPass): # Setting the head of the new linkedlist self.head = next_node.prev firstPass = False else: prevFirst.next = prev_node prevFirst = first return self.headif __name__ == '__main__': llist = LinkedList() # Insert 6. So linked list becomes 6->NULL llist.append(6) # Insert 7 at the beginning. So # linked list becomes 7->6->NULL llist.push(7) # Insert 1 at the beginning. So # linked list becomes 1->7->6->NULL llist.push(1) # Insert 4 at the end. So linked # list becomes 1->7->6->4->NULL llist.append(4) # Insert 8, after 7. So linked # list becomes 1->7->8->6->4->NULL llist.insertAfter(llist.head.next, 8) # list becomes 1->7->8->6->4->9->NULL llist.append(9) llist.reverseK(2) llist.printList() # This code is contributed by lokesh (lokeshmvs21). |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{ // A linked list node class Node { public int data; public Node next; public Node prev; }; static Node head = null; // Given a reference (pointer to pointer) // to the head of a list // and an int, inserts a new node on the // front of the list. static void push(int new_data) { // Allocate node Node new_node = new Node(); // Put in the data new_node.data = new_data; // Make next of new node as head // and previous as null new_node.next = head; new_node.prev = null; // 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; } // Given a node as prev_node, insert // a new node after the given node static void insertAfter(Node prev_node, int new_data) { // Check if the given prev_node is null if (prev_node == null) { Console.Write("the given previous " + "node cannot be null"); return; } // Allocate new node Node new_node = new Node(); // Put in the data new_node.data = new_data; // Make next of new node as next of prev_node new_node.next = prev_node.next; // Make the next of prev_node as new_node prev_node.next = new_node; // Make prev_node as previous of new_node new_node.prev = prev_node; // Change previous of new_node's next node if (new_node.next != null) new_node.next.prev = new_node; } // Given a reference (pointer to pointer) to the head // of a DLL and an int, appends a new node at the end static void append(int new_data) { // Allocate node Node new_node = new Node(); Node last = head; // Put in the data new_node.data = new_data; // This new node is going to be the last node, // so make next of it as null new_node.next = null; // If the Linked List is empty, // then make the new // node as head if (head == null) { new_node.prev = null; head = new_node; return; } // Else traverse till the last node while (last.next != null) last = last.next; // Change the next of last node last.next = new_node; // Make last node as previous of new node new_node.prev = last; return; } // This function prints contents of // linked list starting from the given node static void printList(Node node) { Node last = new Node(); while (node != null) { Console.Write(" " + node.data+ " "); last = node; node = node.next; } } static Node reverseK(Node head, int k) { // When head is null or linked list // has a single node we return if (head == null || head.next == null) return head; // PrevFirst pointer keeps track of // the node that is to be connected to each // reversed part. Node prevFirst = null, curr = head; // FirstPass variable is used so that we // can mark head of the new linkedlist. bool firstPass = true; while (curr != null) { int count = 0; // Next keeps track of the next node of curr // Prev keeps track of the previous node of curr Node first = curr, next = null, prev = null; while (curr != null && count < k) { // Reversing the doubly linked list by just // swapping their next and prev pointers next = curr.next; if (count == 0) curr.next = null; else curr.next = curr.prev; curr.prev = next; prev = curr; curr = next; count++; } if (firstPass) { // Setting the head of the new linkedlist head = next.prev; firstPass = false; } else { prevFirst.next = prev; } prevFirst = first; } return head; } // Driver Code public static void Main(String[] args) { // Start with the empty list head = null; // Insert 6. So linked list becomes 6.null append( 6); // Insert 7 at the beginning. So // linked list becomes 7.6.null push(7); // Insert 1 at the beginning. So // linked list becomes 1.7.6.null push(1); // Insert 4 at the end. So linked // list becomes 1.7.6.4.null append( 4); // Insert 8, after 7. So linked // list becomes 1.7.8.6.4.null insertAfter(head.next, 8); // list becomes 1.7.8.6.4.9.null append( 9); head = reverseK(head, 2); printList(head); }}// This code is contributed by 29AjayKumar |
Javascript
// JavaScript program for the above approachclass Node{ constructor(data){ this.data = data; this.next = null; this.prev = null; }}// Given a reference (pointer to pointer)// to the head of a list// and an int, inserts a new node on the// front of the list.function push(head_ref, new_data){ // allocate node let new_node = new Node(new_data); // make next of new node as head new_node.next = head_ref; // change prev of head node to new node if(head_ref != null) head_ref.prev = new_node; head_ref = new_node; return head_ref;}// Given a node as prev_node, insert// a new node after the given nodefunction insertAfter(prev_node, new_data){ // check if the given prev_node is null if(prev_node == null){ document.write("the given previous node cannot be NULL"); return; } // allocate new node let new_node = new Node(new_data); // make next of new node as next of prev_node new_node.next = prev_node.next; // make the next of prev_node as new_node prev_node.next = new_node; // make prev_node as previous of new_node new_node.prev = prev_node; // change previous of new_node's next node if(new_node.next != null){ new_node.next.prev = new_node; }}// Given a reference (pointer to pointer) to the head// of a DLL and an int, appends a new node at the endfunction append(head_ref, new_data){ // Allocate node let new_node = new Node(new_data); let last = head_ref; // This new node is going to be the last node, // so make next of it as null new_node.next = null; // If the Linked List is empty, // then make the new // node as head if (head_ref == null) { new_node.prev = null; head_ref = new_node; return head_ref; } // Else traverse till the last node while (last.next != null) last = last.next; // Change the next of last node last.next = new_node; // Make last node as previous of new node new_node.prev = last; return head_ref;}// This function prints contents of// linked list starting from the given nodefunction printList(node){ let last; while(node != null){ document.write(node.data + " "); last = node; node = node.next; }}function reverseK(head, k){ // When head is NULL or linked list // has a single node we return if(head == null || head.next == null) return head; // PrevFirst pointer keeps track of // the node that is to be connected to each // reversed part. let prevFirst = null; let curr = head; // FirstPass variable is used so that we // can mark head of the new linkedlist. let firstPass = true; while(curr != null){ let count = 0; // Next keeps track of the next node of curr // Prev keeps track of the previous node of curr let first = curr; let next = null; let prev = null; while(curr != null && count < k){ // Reversing the doubly linked list by just // swapping their next and prev pointers next = curr.next; if(count == 0){ curr.next = null; } else{ curr.next = curr.prev; } curr.prev = next; prev = curr; curr = next; count++; } if(firstPass){ // Setting the head of the new linkedlist head = next.prev; firstPass = false; }else{ prevFirst.next = prev; } prevFirst = first; } return head;}// driver code// start with the empty listlet head = null;// Insert 6. So linked list becomes 6->NULLhead = append(head, 6);// Insert 7 at the beginning. So// linked list becomes 7->6->NULLhead = push(head, 7);// Insert 1 at the beginning. So// linked list becomes 1->7->6->NULLhead = push(head, 1);// Insert 4 at the end. So linked// list becomes 1->7->6->4->NULLhead = append(head, 4);// Insert 8, after 7. So linked// list becomes 1->7->8->6->4->NULLinsertAfter(head.next, 8);// list becomes 1->7->8->6->4->9->NULLhead = append(head, 9);head = reverseK(head, 2);printList(head);// This code is contributed by Kirti Agarwal |
Output
7 1 6 8 9 4
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
