Given a singly linked list and two integers X and Y, the task is to left rotate the linked list by X in groups of Y nodes.
Examples:
Input: 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> 70 -> 80 -> 90 -> 100, X = 2, Y = 4
Output: 30 -> 40 -> 10 -> 20 -> 70 -> 80 -> 50 -> 60 -> 90 -> 100
Explanation: First group of nodes is 10->20->30->40.
After rotating by 2, it becomes 30->40->10->20.
Second group of nodes is 50->60->70->80.
After rotating by 2, it becomes 70->80->50->60.
Third group of nodes is 90->100.
After rotating by 2, it becomes 90->100.Input: 40 -> 60 -> 70 -> 80 -> 90 -> 100, X = 1, Y = 3
Output: 70 -> 40 -> 60 -> 100 -> 80 -> 90
Approach: The problem can be solved by using reversal algorithm for rotation based on the below observation:
Let A1 -> B1 -> A2 -> B2 ->…….-> AnBn represents the complete list where, AiBi represents a group of Y nodes, and Ai and Bi represents the separate parts of this group at the node of rotation i.e. Ai has X nodes and Bi has (Y – X) nodes.
For all Ai and Bi such that 1 ≤ i ≤ N
- Reverse A and B of size X and (Y-X) nodes to get ArBr, where Ar and Br are reverse of A and B respectively,
- Reverse ArBr of size Y to get BA.
Follow the image shown below for a better understanding
Rotate linked list by 2 nodes in groups of 4 nodes
Follow the steps mentioned below to solve the problem:
- Traverse the linked list from start:
- Select the groups of Y nodes:
- Use reversal approach for rotation in these groups to left rotate by X positions.
- Move to the next group of Y nodes.
- Return the final linked list.
Below is the implementation of the above approach:
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; // Structure of node of singly linked list struct Node { int data; Node* next; Node(int x) { data = x; next = NULL; }};// Function to reverse a list in// alternate groups of size m and nNode* reverse(Node* head, int m, int n, bool isfirstHalf){ if(!head){ return NULL; } Node* current = head; Node* next = NULL; Node* prev = NULL; int count = 0, k = m; if(!isfirstHalf){ k = n; } // Reverse first k nodes of linked list while(count < k && current != NULL){ next = current->next; current->next = prev; prev = current; current = next; count++; } // Next is now a pointer // to (k+1)th node // Recursively call for the list // starting from current and // make rest of the list // as next of first node. if(next){ head->next = reverse(next, m, n, !isfirstHalf); } // prev is now head of input list return prev;}// Function to left rotate a list// by x nodes in groups of yNode* leftRotate(Node *head, int x, int y){ Node* prev = reverse(head, x, y-x, true); return reverse(prev, y, y, true);}// Function to push a new node// on the front of the list.void push(Node** head, int new_data){ Node* new_node = new Node(new_data); new_node->next = *head; *head = new_node;}// Function to print listvoid printList(Node* head){ Node* temp = head; while(temp){ cout << temp->data << " "; temp = temp->next; } cout << endl;}// Driver code int main() { Node* head = NULL; // Create a list // 10->20->30->40->50->60 // ->70->80->90->100 for(int i=100 ; i>=10 ; i-=10){ push(&head, i); } cout << "Given list" << endl; printList(head); head = leftRotate(head, 2, 4); cout << "Rotated Linked List" << endl; printList(head); return 0; }// This code is contributed by subhamgoyal2014. |
Java
// Java program to rotate a linked listimport java.io.*;public class LinkedList { Node head; // Linked list Node public class Node { int data; Node next; Node(int d) { data = d; next = null; } } // Function to left rotate a list // by x nodes in groups of y Node leftRotate(int x, int y) { Node prev = reverse(head, x, y - x, true); return reverse(prev, y, y, true); } // Function to reverse list in // alternate groups of size m and n Node reverse(Node head, int m, int n, boolean isfirstHalf) { if (head == null) return null; Node current = head; Node next = null; Node prev = null; int count = 0, k = m; if (!isfirstHalf) k = n; // Reverse first k nodes of linked list while (count < k && current != null) { next = current.next; current.next = prev; prev = current; current = next; count++; } // Next is now a pointer // to (k+1)th node // Recursively call for the list // starting from current and // make rest of the list // as next of first node if (next != null) head.next = reverse(next, m, n, !isfirstHalf); // prev is now head of input list return prev; } // Function to push a new node // on the front of the list. 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(); // Create a list // 10->20->30->40->50->60 // ->70->80->90->100 for (int i = 100; i >= 10; i -= 10) llist.push(i); System.out.println("Given list"); llist.printList(); llist.head = llist.leftRotate(2, 4); System.out.println("Rotated Linked List"); llist.printList(); }}// This code is contributed by Pushpesh Raj |
C#
// C# program to rotate a linked listusing System;public class LinkedList { Node head; // Linked list Node public class Node { public int data; public Node next; public Node(int d) { data = d; next = null; } } // Function to left rotate a list // by x nodes in groups of y Node leftRotate(int x, int y) { Node prev = reverse(head, x, y - x, true); return reverse(prev, y, y, true); } // Function to reverse list in // alternate groups of size m and n Node reverse(Node head, int m, int n, bool isfirstHalf) { if (head == null) return null; Node current = head; Node next = null; Node prev = null; int count = 0, k = m; if (!isfirstHalf) k = n; // Reverse first k nodes of linked list while (count < k && current != null) { next = current.next; current.next = prev; prev = current; current = next; count++; } // Next is now a pointer // to (k+1)th node // Recursively call for the list // starting from current and // make rest of the list // as next of first node if (next != null) head.next = reverse(next, m, n, !isfirstHalf); // prev is now head of input list return prev; } // Function to push a new node // on the front of the list. 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 public static void Main() { LinkedList llist = new LinkedList(); // Create a list // 10->20->30->40->50->60 // ->70->80->90->100 for (int i = 100; i >= 10; i -= 10) llist.push(i); Console.WriteLine("Given list"); llist.printList(); llist.head = llist.leftRotate(2, 4); Console.WriteLine("Rotated Linked List"); llist.printList(); }} |
Python3
# Python program to rotate a linked list# Linked list Nodeclass Node : def __init__(self,d): self.data = d self.next = Noneclass LinkedList : def __init__(self): self.head = None # Function to left rotate a list # by x nodes in groups of y def leftRotate(self,x,y): prev = self.reverse(self.head, x, y - x, True) return self.reverse(prev, y, y, True) # Function to reverse list in # alternate groups of size m and n def reverse(self,head,m,n,isfirstHalf): if (head == None): return None current = head next = None prev = None count,k = 0,m if (isfirstHalf == False): k = n # Reverse first k nodes of linked list while (count < k and current != None) : next = current.next current.next = prev prev = current current = next count += 1 # Next is now a pointer # to (k+1)th node # Recursively call for the list # starting from current and # make rest of the list # as next of first node if (next != None): head.next = self.reverse(next, m, n,~isfirstHalf) # prev is now head of input list return prev # Function to push a new node # on the front of the list. 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 = " ") temp = temp.next print()# Driver codellist = LinkedList()# Create a list# 10->20->30->40->50->60# ->70->80->90->100for i in range(100,9,-10): llist.push(i)print("Given list")llist.printList()llist.head = llist.leftRotate(2, 4)print("Rotated Linked List")llist.printList()# This code is contributed by shinjanpatra |
Javascript
<script>// JavaScript program to rotate a linked list// Linked list Nodeclass Node { constructor(d) { this.data = d; this.next = null; }}class LinkedList { constructor(){ this.head = null; } // Function to left rotate a list // by x nodes in groups of y leftRotate(x,y) { let prev = this.reverse(this.head, x, y - x, true); return this.reverse(prev, y, y, true); } // Function to reverse list in // alternate groups of size m and n reverse(head,m,n,isfirstHalf) { if (head == null) return null; let current = head; let next = null; let prev = null; let count = 0, k = m; if (!isfirstHalf) k = n; // Reverse first k nodes of linked list while (count < k && current != null) { next = current.next; current.next = prev; prev = current; current = next; count++; } // Next is now a pointer // to (k+1)th node // Recursively call for the list // starting from current and // make rest of the list // as next of first node if (next != null) head.next = this.reverse(next, m, n, !isfirstHalf); // prev is now head of input list return prev; } // Function to push a new node // on the front of the list. push(new_data) { let new_node = new Node(new_data); new_node.next = this.head; this.head = new_node; } // Function to print list printList() { let temp = this.head; while (temp != null) { document.write(temp.data," "); temp = temp.next; } document.write("</br>"); }}// Driver codelet llist = new LinkedList();// Create a list// 10->20->30->40->50->60// ->70->80->90->100for (let i = 100; i >= 10; i -= 10) llist.push(i);document.write("Given list","</br>");llist.printList();llist.head = llist.leftRotate(2, 4);document.write("Rotated Linked List","</br>");llist.printList();// This code is contributed by shinjanpatra</script> |
Output
Given list 10 20 30 40 50 60 70 80 90 100 Rotated Linked List 30 40 10 20 70 80 50 60 90 100
Time Complexity: O(N) where N is the length of the linked list
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!
