Reverse a Linked List in groups of given size using Deque

Last Updated : 12 Sep, 2024

Given a Singly linked list containing n nodes. The task is to reverse every group of k nodes in the list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should be considered as a group and must be reversed.

Examples:

Input: head: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL, k = 2
Output: head: 2 -> 1 -> 4 -> 3 -> 6 -> 5 -> NULL
Explanation : Linked List is reversed in a group of size k = 2.

Input: head: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL, k = 4
Output: head: 4 -> 3 -> 2 -> 1 -> 6 -> 5 -> NULL
Explanation : Linked List is reversed in a group of size k = 4.

Approach:

The idea is to reverse a linked list in groups of size k using a deque. For each group of size k, store nodes in the deque, then repeatedly swap the data of the first and last nodes by popping from both ends of the deque. Continue this process until all nodes are traversed.

Follow the steps below to solve the problem:

Initialize a deque(double-ended queue) of node type.
Store the address of the first k nodes in the deque.
Pop first and the last value from the deque and swap the data values at those addresses.
Repeat step 3 till the deque is not empty.
Repeat step 2 for the next k nodes and till we reach to end of the linked list.

Below is the implementation of the above approach:

C++

// C++ program to reverse a linked list in // groups of given size #include <bits/stdc++.h> using namespace std; class Node {  public:  int data;  Node *next;  Node(int x) {  data = x;  next = nullptr;  } }; // Function to reverse the linked list in // groups using deque Node *reverseKGroup(Node *head, int k) {  if (!head || k == 1) {  return head;  }  deque<Node*> dq;   Node *curr = head;  while (curr != nullptr) {  int count = 0;  // Push k nodes into the deque  while (curr != nullptr && count < k) {  dq.push_back(curr);  curr = curr->next;  count++;  }    // Swap first and last nodes in the deque   while (!dq.empty()) {  Node* front = dq.front();  Node* last = dq.back();  swap(front->data, last->data);  // Pop from the front and back of the deque  if (!dq.empty()) {  dq.pop_front();  }  if (!dq.empty()) {  dq.pop_back();  }  }  }    return head; } void printList(Node *head) {  Node *curr = head;  while (curr != nullptr) {  cout << curr->data << " ";  curr = curr->next;  }  cout << endl; } int main() {    // Creating a sample singly linked list:  // 1 -> 2 -> 3 -> 4 -> 5 -> 6  Node *head = new Node(1);  head->next = new Node(2);  head->next->next = new Node(3);  head->next->next->next = new Node(4);  head->next->next->next->next = new Node(5);  head->next->next->next->next->next = new Node(6);  head = reverseKGroup(head, 3);    printList(head);  return 0; }

Java

// Java program to reverse a linked list // in groups of given size import java.util.Deque; import java.util.LinkedList; class Node {  int data;  Node next;  Node(int x) {  data = x;  next = null;  } } class GfG {  // Function to reverse the linked list  // in groups using deque  static Node reverseKGroup(Node head, int k) {  if (head == null || k == 1) {  return head;  }  Deque<Node> dq = new LinkedList<>();  Node curr = head;  while (curr != null) {  int count = 0;  // Push k nodes into the deque  while (curr != null && count < k) {  dq.addLast(curr);  curr = curr.next;  count++;  }  // Swap first and last nodes in the deque  while (!dq.isEmpty()) {  Node front = dq.peekFirst();  Node last = dq.peekLast();  swap(front, last);     if (!dq.isEmpty()) dq.pollFirst();  if (!dq.isEmpty()) dq.pollLast();  }  }  return head;  }  static void swap(Node a, Node b) {  int temp = a.data;  a.data = b.data;  b.data = temp;  }  static void printList(Node head) {  Node curr = head;  while (curr != null) {  System.out.print(curr.data + " ");  curr = curr.next;  }  System.out.println();  }  public static void main(String[] args) {    // Creating a sample singly linked list:  // 1 -> 2 -> 3 -> 4 -> 5 -> 6   Node head = new Node(1);  head.next = new Node(2);  head.next.next = new Node(3);  head.next.next.next = new Node(4);  head.next.next.next.next = new Node(5);  head.next.next.next.next.next = new Node(6);  head = reverseKGroup(head, 3);  printList(head);  } }

Python

# Python program to reverse a linked list in # groups of given size from collections import deque class Node: def __init__(self, x): self.data = x self.next = None # Function to reverse the linked list in # groups using deque def reverseKGroup(head, k): if not head or k == 1: return head dq = deque() curr = head while curr: count = 0 # Push k nodes into the deque while curr and count < k: dq.append(curr) curr = curr.next count += 1 # Swap first and last nodes in the deque while dq: front = dq[0] last = dq[-1] front.data, last.data = last.data, front.data if dq: dq.popleft() if dq: dq.pop() return head def printList(head): curr = head while curr: print(curr.data, end=" ") curr = curr.next print() if __name__ == "__main__": # Creating a sample singly linked list: # 1 -> 2 -> 3 -> 4 -> 5 -> 6  head = Node(1) head.next = Node(2) head.next.next = Node(3) head.next.next.next = Node(4) head.next.next.next.next = Node(5) head.next.next.next.next.next = Node(6) head = reverseKGroup(head, 3) printList(head)

// C# program to reverse a linked list in groups using System; using System.Collections.Generic; class Node {  public int data;  public Node next;  public Node(int x) {  data = x;  next = null;  } } class GfG {  // Function to reverse the linked list in groups   static Node reverseKGroup(Node head, int k) {  if (head == null || k == 1)  return head;  List<Node> q = new List<Node>();  Node curr = head;  while (curr != null) {  int count = 0;  // Store addresses of the k nodes in the list  while (count < k && curr != null) {  q.Add(curr);  curr = curr.next;  count++;  }  // Swap first and last nodes in the list  while (q.Count > 0) {  Node front = q[0];  Node last = q[q.Count - 1];  // Swapping data between the front and last nodes  int temp = front.data;  front.data = last.data;  last.data = temp;  // Remove from the front and back of the list  q.RemoveAt(0);  if (q.Count > 0) {  q.RemoveAt(q.Count - 1);  }  }  }  return head;  }  static void printList(Node head) {  Node curr = head;  while (curr != null) {  Console.Write(curr.data + " ");  curr = curr.next;  }  Console.WriteLine();  }  static void Main(string[] args) {    // Creating a sample singly linked list:  // 1 -> 2 -> 3 -> 4 -> 5 -> 6  Node head = new Node(1);  head.next = new Node(2);  head.next.next = new Node(3);  head.next.next.next = new Node(4);  head.next.next.next.next = new Node(5);  head.next.next.next.next.next = new Node(6);  head = reverseKGroup(head, 3);  printList(head);  } }

JavaScript

// JavaScript program to reverse a linked  // list in groups of given size class Node {  constructor(x) {  this.data = x;  this.next = null;  } } // Function to reverse the linked list // in groups using deque function reverseKGroup(head, k) {  if (!head || k === 1) {  return head;  }  let dq = [];  let curr = head;  while (curr) {  let count = 0;  // Push k nodes into the deque  while (curr && count < k) {  dq.push(curr);  curr = curr.next;  count++;  }  // Swap first and last nodes in the deque  while (dq.length) {  let front = dq[0];  let last = dq[dq.length - 1];  [front.data, last.data] = [last.data, front.data];  dq.shift();   dq.pop();   }  }  return head; } // Helper function to print the linked list function printList(head) {  let curr = head;  while (curr) {  console.log(curr.data);  curr = curr.next;  }  console.log(); } // Creating a sample singly linked list: // 1 -> 2 -> 3 -> 4 -> 5 -> 6 let head = new Node(1); head.next = new Node(2); head.next.next = new Node(3); head.next.next.next = new Node(4); head.next.next.next.next = new Node(5); head.next.next.next.next.next = new Node(6); head = reverseKGroup(head, 3); printList(head);