Given the linked list and an array arr[] of size N, the task is to reverse every arr[i] nodes of the list at a time (0 ≤ i < N).
Note: If the number of nodes in the list is greater than the sum of array, then the remaining nodes will remain as it is.
Examples:
Input: head = 1->2->3->4->5->6->7->8->9, arr[] = {2, 3, 3}
Output: 2->1->5->4->3->8->7->6->9
Explanation: The first group of size 2 is 1->2. Upon reversing it becomes 2->1.
The next group of size 3 is 3->4->5 which on reversing becomes 5->4->3.
The last group of size 3 is 6->7->8 which on reversing becomes 8->7->6.Input: head = 6->8->7, arr[] = {1, 2}
Output: 6->7->8
Approach: The solution to the problem is based on the idea of selecting groups of nodes of arr[i] size and considering each sublist as an individual linked list and using the concept of reversing a linked list.
Follow the illustration below for a better understanding:
Illustration:
reverse(head, arr, n, index)
Follow the steps mentioned below to implement the idea:
- Traverse through the array from i = 0 to N:
- Reverse the sub-list of size arr[i].
- While reversing the sub-list, for each node, interchange the pointers pointing to the next node and the previous node.
- Reverse the sub-list of size arr[i].
- If the end of the array is reached, stop iteration and return the head pointer of the final list.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Structure of a Binary Tree Nodestruct Node { int data; Node* next; Node(int d) { data = d; next = NULL; }};struct LinkedList { Node* head; LinkedList() { head = NULL; } // Function to reverse a node Node* reverse(Node* head, int arr[], int size, int index) { if (head == NULL) return NULL; Node* current = head; Node* next = NULL; Node* prev = NULL; int count = 0; while (current != NULL && index < size && count < arr[index]) { next = current->next; current->next = prev; prev = current; current = next; count++; } if (index >= size) { while (current != NULL) { next = current->next; current->next = prev; prev = current; current = next; count++; } } if (next != NULL) { head->next = reverse(next, arr, size, index + 1); } return prev; } // Function to push a node void push(int new_data) { Node* new_node = new Node(new_data); new_node->next = head; head = new_node; } // Function to print list void printList() { Node* temp = head; while (temp != NULL) { cout << temp->data << "->"; temp = temp->next; } cout << endl; }}; // Driver program int main() { LinkedList llist; int arr[] = { 2, 3, 3 }; int size = sizeof(arr)/sizeof(arr[0]); llist.push(9); llist.push(8); llist.push(7); llist.push(6); llist.push(5); llist.push(4); llist.push(3); llist.push(2); llist.push(1); llist.head = llist.reverse(llist.head, arr, size, 0); llist.printList(); return 0; }// This code is contributed by jana_sayantan. |
Java
// Java code to implement the approachimport java.io.*;public class LinkedList { Node head; // Node Class static class Node { int data; Node next; Node(int d) { data = d; next = null; } } // Function to reverse a node Node reverse(Node head, int[] arr, int size, int index) { if (head == null) return null; Node current = head; Node next = null; Node prev = null; int count = 0; while (current != null && index < size && count < arr[index]) { next = current.next; current.next = prev; prev = current; current = next; count++; } if (index >= size) { while (current != null) { next = current.next; current.next = prev; prev = current; current = next; count++; } } if (next != null) { head.next = reverse(next, arr, size, index + 1); } return prev; } // Function to push a node public void push(int new_data) { Node new_node = new Node(new_data); new_node.next = head; head = new_node; } // Function to print list void printList() { Node temp = head; while (temp != null) { System.out.print(temp.data + "->"); temp = temp.next; } System.out.println(); } // Driver code public static void main(String[] args) { LinkedList llist = new LinkedList(); int[] arr = { 2, 3, 3 }; int size = arr.length; llist.push(9); llist.push(8); llist.push(7); llist.push(6); llist.push(5); llist.push(4); llist.push(3); llist.push(2); llist.push(1); llist.head = llist.reverse(llist.head, arr, size, 0); llist.printList(); }}// This code is contributed by karandeep123. |
Python3
# Python code for the above approach# Node Classclass Node: def __init__(self, d): self.data = d self.next = None class LinkedList: def __init__(self): self.head = None ## Function to push a node def push(self, new_data): new_node = Node(new_data); new_node.next = self.head; self.head = new_node; ## Function to print list def printList(self): temp = self.head while temp != None: print(temp.data, end='') if temp.next != None: print("->", end='') temp = temp.next print("\n") ## Function to reverse a node def reverse(self, head, arr, size, index): if (head == None): return None current = head next = None prev = None count = 0 while current != None and index < size and count < arr[index]: next = current.next current.next = prev prev = current current = next count+=1 if (index >= size): while current != None: next = current.next current.next = prev prev = current current = next count+=1 if next != None: head.next = self.reverse(next, arr, size, index + 1); return prev;# Driver Codeif __name__=='__main__': llist = LinkedList() arr = [2, 3, 3] size = len(arr) llist.push(9) llist.push(8) llist.push(7) llist.push(6) llist.push(5) llist.push(4) llist.push(3) llist.push(2) llist.push(1) llist.head = llist.reverse(llist.head, arr, size, 0) llist.printList() # This code is contributed by subhamgoyal2014. |
C#
// C# code to implement the approachusing System;using System.Linq;public class LinkedList { Node head; // Node Class class Node { public int data; public Node next; public Node(int d) { data = d; next = null; } } // Function to reverse a node Node reverse(Node head, int[] arr, int size, int index) { if (head == null) return null; Node current = head; Node next = null; Node prev = null; int count = 0; while (current != null && index < size && count < arr[index]) { next = current.next; current.next = prev; prev = current; current = next; count++; } if (index >= size) { while (current != null) { next = current.next; current.next = prev; prev = current; current = next; count++; } } if (next != null) { head.next = reverse(next, arr, size, index + 1); } return prev; } // Function to push a node public void push(int new_data) { Node new_node = new Node(new_data); new_node.next = head; head = new_node; } // Function to print list void printList() { Node temp = head; while (temp != null) { Console.Write(temp.data + "->"); temp = temp.next; } Console.WriteLine(); } // Driver code static void Main() { LinkedList llist = new LinkedList(); int[] arr = { 2, 3, 3 }; int size = arr.Count(); llist.push(9); llist.push(8); llist.push(7); llist.push(6); llist.push(5); llist.push(4); llist.push(3); llist.push(2); llist.push(1); llist.head = llist.reverse(llist.head, arr, size, 0); llist.printList(); }}// This code is contributed by Karandeep1234 |
Javascript
// Javascript code to implement the approach// Structure of a Binary Tree Nodeclass Node { constructor(d) { this.data = d; this.next = null; }};// Function to reverse a nodefunction reverse(head,arr,size,index){ if (head == null) return null; let current = head; let next = null; let prev = null; let count = 0; while (current != null && index < size && count < arr[index]) { next = current.next; current.next = prev; prev = current; current = next; count++; } if (index >= size) { while (current != null) { next = current.next; current.next = prev; prev = current; current = next; count++; } } if (next != null) { head.next = reverse(next, arr, size, index + 1); } return prev;}class LinkedList { constructor() { this.head = null; } // Function to push a node push(new_data) { let new_node = new Node(new_data); new_node.next = this.head; this.head = new_node; } // Function to print list printList() { var curr = this.head; var str = ""; while (curr) { str += curr.data + "->"; curr = curr.next; } console.log(str); }} // Driver program let llist= new LinkedList(); let arr = [ 2, 3, 3 ]; let size = 3; llist.push(9); llist.push(8); llist.push(7); llist.push(6); llist.push(5); llist.push(4); llist.push(3); llist.push(2); llist.push(1); llist.head = reverse(llist.head, arr, size, 0); llist.printList(); // This code is contributed by Ishan Khandelwal. |
Output
2->1->5->4->3->8->7->6->9->
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!
