Given a linked list and two positions ‘m’ and ‘n’. The task is to rotate the sublist from position m to n, to the right by k places.
Examples:
Input: list = 1->2->3->4->5->6, m = 2, n = 5, k = 2
Output: 1->4->5->2->3->6
Rotate the sublist 2 3 4 5 towards right 2 times
then the modified list are: 1 4 5 2 3 6Input: list = 20->45->32->34->22->28, m = 3, n = 6, k = 3
Output: 20->45->34->22->28->32
Rotate the sublist 32 34 22 28 towards right 3 times
then the modified list are: 20 45 34 22 28 32
Approach: For rotating the given sublist that extends from m to n element, move the list from (n-k+1)th to nth node to starting of sub-list to finish the rotation.
If k is greater than size of sublist then we will take its modulo with size of sublist. So traverse through list using a pointer and a counter and we will save (m-1)th node and later make it point to (n-k+1)th node and hence bring (n-k+1)th node to the start(front) of sublist.
Similarly we will save mth node and later make nth node point to it. And for keeping rest of list intact we will make (n-k)th node point to next node of n (maybe NULL). And finally we will get the k times right rotated sublist.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Definition of node of linkedliststruct ListNode { int data; struct ListNode* next;};// This function take head pointer of list, start and// end points of sublist that is to be rotated and the// number k and rotate the sublist to right by k places.void rotateSubList(ListNode* A, int m, int n, int k){ int size = n - m + 1; // If k is greater than size of sublist then // we will take its modulo with size of sublist if (k > size) { k = k % size; } // If k is zero or k is equal to size or k is // a multiple of size of sublist then list // remains intact if (k == 0 || k == size) { ListNode* head = A; while (head != NULL) { cout << head->data; head = head->next; } return; } ListNode* link = NULL; // m-th node if (m == 1) { link = A; } // This loop will traverse all node till // end node of sublist. ListNode* c = A; // Current traversed node int count = 0; // Count of traversed nodes ListNode* end = NULL; ListNode* pre = NULL; // Previous of m-th node while (c != NULL) { count++; // We will save (m-1)th node and later // make it point to (n-k+1)th node if (count == m - 1) { pre = c; link = c->next; } if (count == n - k) { if (m == 1) { end = c; A = c->next; } else { end = c; // That is how we bring (n-k+1)th // node to front of sublist. pre->next = c->next; } } // This keeps rest part of list intact. if (count == n) { ListNode* d = c->next; c->next = link; end->next = d; ListNode* head = A; while (head != NULL) { cout << head->data << " "; head = head->next; } return; } c = c->next; }}// Function for creating and linking new nodesvoid push(struct ListNode** head, int val){ struct ListNode* new_node = new ListNode; new_node->data = val; new_node->next = (*head); (*head) = new_node;}// Driver codeint main(){ struct ListNode* head = NULL; push(&head, 70); push(&head, 60); push(&head, 50); push(&head, 40); push(&head, 30); push(&head, 20); push(&head, 10); ListNode* tmp = head; cout << "Given List: "; while (tmp != NULL) { cout << tmp->data << " "; tmp = tmp->next; } cout << endl; int m = 3, n = 6, k = 2; cout << "After rotation of sublist: "; rotateSubList(head, m, n, k); return 0;} |
Java
// Java implementation of the above approach import java.util.*;class Solution{ // Definition of node of linkedlist static class ListNode { int data; ListNode next; } // This function take head pointer of list, start and // end points of sublist that is to be rotated and the // number k and rotate the sublist to right by k places. static void rotateSubList(ListNode A, int m, int n, int k) { int size = n - m + 1; // If k is greater than size of sublist then // we will take its modulo with size of sublist if (k > size) { k = k % size; } // If k is zero or k is equal to size or k is // a multiple of size of sublist then list // remains intact if (k == 0 || k == size) { ListNode head = A; while (head != null) { System.out.print( head.data); head = head.next; } return; } ListNode link = null; // m-th node if (m == 1) { link = A; } // This loop will traverse all node till // end node of sublist. ListNode c = A; // Current traversed node int count = 0; // Count of traversed nodes ListNode end = null; ListNode pre = null; // Previous of m-th node while (c != null) { count++; // We will save (m-1)th node and later // make it point to (n-k+1)th node if (count == m - 1) { pre = c; link = c.next; } if (count == n - k) { if (m == 1) { end = c; A = c.next; } else { end = c; // That is how we bring (n-k+1)th // node to front of sublist. pre.next = c.next; } } // This keeps rest part of list intact. if (count == n) { ListNode d = c.next; c.next = link; end.next = d; ListNode head = A; while (head != null) { System.out.print( head.data+" "); head = head.next; } return; } c = c.next; } } // Function for creating and linking new nodes static ListNode push( ListNode head, int val) { ListNode new_node = new ListNode(); new_node.data = val; new_node.next = (head); (head) = new_node; return head;} // Driver code public static void main(String args[]){ ListNode head = null; head =push(head, 70); head =push(head, 60); head =push(head, 50); head =push(head, 40); head =push(head, 30); head =push(head, 20); head =push(head, 10); ListNode tmp = head; System.out.print("Given List: "); while (tmp != null) { System.out.print( tmp.data + " "); tmp = tmp.next; } System.out.println(); int m = 3, n = 6, k = 2; System.out.print( "After rotation of sublist: "); rotateSubList(head, m, n, k); } }// This code is contributed// by Arnab Kundu |
Python3
# Python3 implementation of the above approachimport math# Definition of node of linkedlistclass Node: def __init__(self, data): self.data = data self.next = None# This function take head pointer of list, # start and end points of sublist that is # to be rotated and the number k and# rotate the sublist to right by k places.def rotateSubList(A, m, n, k): size = n - m + 1 # If k is greater than size of sublist then # we will take its modulo with size of sublist if (k > size): k = k % size # If k is zero or k is equal to size or k is # a multiple of size of sublist then list # remains intact if (k == 0 or k == size): head = A while (head != None): print(head.data) head = head.next return link = None # m-th node if (m == 1) : link = A # This loop will traverse all node till # end node of sublist. c = A # Current traversed node count = 0 # Count of traversed nodes end = None pre = None # Previous of m-th node while (c != None) : count = count + 1 # We will save (m-1)th node and later # make it point to (n-k+1)th node if (count == m - 1) : pre = c link = c.next if (count == n - k) : if (m == 1) : end = c A = c.next else : end = c # That is how we bring (n-k+1)th # node to front of sublist. pre.next = c.next # This keeps rest part of list intact. if (count == n) : d = c.next c.next = link end.next = d head = A while (head != None) : print(head.data, end = " ") head = head.next return c = c.next # Function for creating and linking new nodesdef push(head, val): new_node = Node(val) new_node.data = val new_node.next = head head = new_node return head# Driver codeif __name__=='__main__': head = None head = push(head, 70) head = push(head, 60) head = push(head, 50) head = push(head, 40) head = push(head, 30) head = push(head, 20) head = push(head, 10) tmp = head print("Given List: ", end = "") while (tmp != None) : print(tmp.data, end = " ") tmp = tmp.next print() m = 3 n = 6 k = 2 print("After rotation of sublist: ", end = "") rotateSubList(head, m, n, k)# This code is contributed by Srathore |
C#
// C# implementation of the above approach using System;class GFG{// Definition of node of linkedlist public class ListNode{ public int data; public ListNode next;}// This function take head pointer of list, // start and end points of sublist that is // to be rotated and the number k and rotate // the sublist to right by k places. public static void rotateSubList(ListNode A, int m, int n, int k){ int size = n - m + 1; // If k is greater than size of sublist // then we will take its modulo with // size of sublist if (k > size) { k = k % size; } // If k is zero or k is equal to size // or k is a multiple of size of sublist // then list remains intact if (k == 0 || k == size) { ListNode head = A; while (head != null) { Console.Write(head.data); head = head.next; } return; } ListNode link = null; // m-th node if (m == 1) { link = A; } // This loop will traverse all node till // end node of sublist. ListNode c = A; // Current traversed node int count = 0; // Count of traversed nodes ListNode end = null; ListNode pre = null; // Previous of m-th node while (c != null) { count++; // We will save (m-1)th node and later // make it point to (n-k+1)th node if (count == m - 1) { pre = c; link = c.next; } if (count == n - k) { if (m == 1) { end = c; A = c.next; } else { end = c; // That is how we bring (n-k+1)th // node to front of sublist. pre.next = c.next; } } // This keeps rest part of list intact. if (count == n) { ListNode d = c.next; c.next = link; end.next = d; ListNode head = A; while (head != null) { Console.Write(head.data + " "); head = head.next; } return; } c = c.next; }}// Function for creating and linking new nodes public static ListNode push(ListNode head, int val){ ListNode new_node = new ListNode(); new_node.data = val; new_node.next = (head); (head) = new_node; return head;}// Driver code public static void Main(string[] args){ ListNode head = null; head = push(head, 70); head = push(head, 60); head = push(head, 50); head = push(head, 40); head = push(head, 30); head = push(head, 20); head = push(head, 10); ListNode tmp = head; Console.Write("Given List: "); while (tmp != null) { Console.Write(tmp.data + " "); tmp = tmp.next; } Console.WriteLine(); int m = 3, n = 6, k = 2; Console.Write("After rotation of sublist: "); rotateSubList(head, m, n, k);}}// This code is contributed by Shrikant13 |
Javascript
<script> // JavaScript implementation of the above approach // Definition of node of linkedlist class ListNode { constructor() { this.data = 0; this.next = null; } } // This function take head pointer of list, // start and end points of sublist that is // to be rotated and the number k and rotate // the sublist to right by k places. function rotateSubList(A, m, n, k) { var size = n - m + 1; // If k is greater than size of sublist // then we will take its modulo with // size of sublist if (k > size) { k = k % size; } // If k is zero or k is equal to size // or k is a multiple of size of sublist // then list remains intact if (k == 0 || k == size) { var head = A; while (head != null) { document.write(head.data); head = head.next; } return; } var link = null; // m-th node if (m == 1) { link = A; } // This loop will traverse all node till // end node of sublist. var c = A; // Current traversed node var count = 0; // Count of traversed nodes var end = null; var pre = null; // Previous of m-th node while (c != null) { count++; // We will save (m-1)th node and later // make it point to (n-k+1)th node if (count == m - 1) { pre = c; link = c.next; } if (count == n - k) { if (m == 1) { end = c; A = c.next; } else { end = c; // That is how we bring (n-k+1)th // node to front of sublist. pre.next = c.next; } } // This keeps rest part of list intact. if (count == n) { var d = c.next; c.next = link; end.next = d; var head = A; while (head != null) { document.write(head.data + " "); head = head.next; } return; } c = c.next; } } // Function for creating and linking new nodes function push(head, val) { var new_node = new ListNode(); new_node.data = val; new_node.next = head; head = new_node; return head; } // Driver code var head = null; head = push(head, 70); head = push(head, 60); head = push(head, 50); head = push(head, 40); head = push(head, 30); head = push(head, 20); head = push(head, 10); var tmp = head; document.write("Given List: "); while (tmp != null) { document.write(tmp.data + " "); tmp = tmp.next; } document.write("<br>"); var m = 3, n = 6, k = 2; document.write("After rotation of sublist: "); rotateSubList(head, m, n, k); </script> |
Output:
Given List: 10 20 30 40 50 60 70 After rotation of sublist: 10 20 50 60 30 40 70
Complexity Analysis:
- Time complexity: O(N) where N is the size of the given 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!
