so let's continue with our playlist but before that hey every welcome back to the channel I hope you guys are doing extremely well so the problem that we will be solving today is rotating a given link list so you'll be given a link list and you'll be given the value k your task is to rotate the link list by K times so over here K is two I'll have to rotate it two times so if I rotate it one time this is how the link list will look like so what happens is from the back one element comes out comes to the front and this gets shifted rightwards by one place each so this is how it will look like after one rotation so on this if I do one more rotation the last element will come at the front and the front elements will get shifted by one place ahead so can I say after two rotations this is how the updated link list will look like so your task is to to return the updated head after doing K rotations so you might have a question hey what is the range of K so the range of K can be anything like in this particular example the length is five k can be 1 K can be 5 K can be 10 K can be 100 K can be th as well K can be anything but as of now we will try solving this problem for smaller values of K once you have done that we will see how can we solve it for larger values so K is given us two let's observe what is happening the last two notes are at the front but this is link list we don't care about that if we can see the link changes I think our job will be done so this is the tail note it next is pointing to null after two rotation after two rotations the tail Lo it's next is pointing to the initial head this is the initial head so the first job is to recognize the tail load we can easily do it by doing a simple Travers we start from here and we reach here so we can easily recognize the de lo once you have done that it's next is pointing to null instead of it instead of it I'll make sure this is pointing to the Head this is pointing to the head so we can do that let's try to do it instead of this I'll make sure that this is pointing to the Head done what after this let's visualize we have a three it's pointing to null we have a three here which is pointing to four correct so I have to change this link K is given us two so if you see the last two notes are eliminated If you eliminate the last two notes from your vision this is the note right right before the last two nodes so can I say if the total length is five if I eliminate two I need the third node I need the third node first second third I need the third node so I have to get into that third node Noe Again by traversal I can reach the third node imagine you are standing at this stde which is the third node what is your job your job is to make sure this is pointing to null this is pointing to null but wait wait need to return the updated head you need to return the updated head so what you can do is once you're standing over here you can straight away say hey this will be my updated head you can chase the head from here and you can take it there once you have done that once youve done that you can remove it yes you can remove it and you can make sure Temporaries next is pointing to n temporar next is pointing to n done what will happen so head is here is like four five then goes to one then goes to two then goes to three which is exactly this particular link done and dusted you might be thinking hey what if the value of K is large what if the value of K is more than the length or if it's equivalent to length so let's go back couple of steps so we know how to solve this particular problem for smaller values of K now we need to think about larger values of K what if the value of K is given as five which is basically the length of the link list what will happen can I say if the length is given as five and if I try rotating if I try rotating I'll come back to the original configuration you can try rotating it for five times you will see that you come back to the original configuration so we see that if K is equivalent to the length we don't need to do anything we return the head what if K is 10 it's basically you rotate once for five you'll come back to the original again you rotate for five times you'll again come back to the original so you eventually come back to the original even if you rotate it for 10 times if you rotate it for 15 rotate for five another five another five each like every time you come back to the original configuration so if it is a multiple if it is a multiple of the length if it is a multiple of the length very important if it is a multiple of the length it comes back to the original configuration so you don't need to do anything you just return the given head so that's something that you have to do if your K is modulated with lengths don't need to do anything you straight away return the head that's an edge case that you have to handle what if K is given as 13 can I say I can write it as 5 + 5 + 3 which technically means coming back to its original coming back to its original and you just need to do three rotations you don't need to do 13 rotations you just need to do three rotation now three is a smaller number for which we have solved we solved this particular problem for smaller numbers not understood got it so you have solved this problem for smaller values of K and for larger values of K as well so what is the next thing that we need to do we need to make sure that the algorithm Works what do we need what do we need we need the length so that we can determine this and also we can reduce the value of K in case it's a larger value also we need the tail because we need to do the changes in the length so let's take uh tail to be at the head initially let's take the length to be one let's try mve it ta will go here and length will be updated to length let's move Tail and length will go to the next length will be updated to three tail will go to the next and length will be updated to four tail will go to the next and length will be updated to five understood so tail is standing at the tail and the first traversal is completed so you have the length depending on the length you can perform your H case right if K is given as let's say 14 if K is given us 14 doesn't matter what you need to do is 14 modul 5 you'll get it right so this is your length perfect you have the tail what is the next thing that you'll do the next thing that you'll do is you'll make sure that the tail next is pointing to the Head very simple Tails next to head so one step is done that is taking the tail and making sure its next is pointing to the initial head because after rotation that is how it will look like what is the next job the new last node or rather the new tail node it should be pointing to null so let's first locate the new tail node that's very simple you have to leave out the last two elements so if the length is 5 minus K so you have to find the third element you have to find the third element you can easily do by traversal like you can keep a temporary here and you can keep a counter equal to one let's try moving temporary will move here counter will increase let's again try mov moving temporary will move here counter will increase and this is where you reach and once you have reached here you know that temporary like you're standing at that new last flow once this is done you can update your head to this one and that's very simple Temporaries next will be your new head once this is done make sure Temporaries next is pointing to another none understood quite simple so I'll be writing down the pseudo code it won't be language specific in case you want the C++ Java python or JavaScript codes the link will be in the description what do we need initially we need the length let's assign the length to be one and we need the tail so let's assign the tail to be head correct let's try to Traverse while Tails next is not null because I need to make sure I reach the tail not Beyond it so till it's not null I can do a length plus plus and at the same time I can say a tail equal to Tails next perfect after this what will happen is I'll have the length and I'll also have the tail in case in case k is directly divisible by length we don't do anything we will return the head if it is not the case then we do the link changes how will we do the link changes but before that please make sure that K is modulated by length in case k is a larger value what is the first thing that we will do we'll make sure that the tail next is pointing to head done so I can say that the first step of the operation is done the first step is done now what is your next step relocate the new last load which will basically be your new tail can I probably write a function that finds me the N node I'll pass on the head I need to find length minus K 5 - 2 the third node the third node I write a function like a generic function that will find me it once I've done this what is the job my head will be updated if you remember the head will be updated because four will be my new head please update your head your head will be new last node next perfect what after this this new last node this is this is your new last node right it has to point to that is why it's the last node right done and once this is once this is done you can return the head of the link list perfect quite simple so this is the entire pseudo code now it's time to go back into the code editor and you can see that I've written down the edge case what if the link list is empty or if there are zero rotations in that case written the given head itself and I've written down the generic nth node function where you take the count equal to one and if it's equivalent to your K WR that note otherwise you move ahead increase the count and you move ahead quite simple and this stays the same what I'll do is I'll hit the submit button and this will be accepted let's analyze the time complexity I can say this is definitely a bigo in for sure am I using anything else probably here what if at the worst case k is one in that case to find the nth node you'll have to Travers the entire link nearb so I can say B of n over here and this nth node at the worst case might take B of in so the overall complexity is beo of 2 N any extra space no so that's beo of one so the time complexity is B of 2 and and the space complexity is B of one so if you're still watching I'm very sure that you've understood everything and if that is the case please please do consider giving us a like and if you're new to our Channel what are you waiting for hit that subscribe button with this I'll be wrapping up this video experience the video till then bye-bye take care [Music] brenen