Linked List data structures and algorithms for Programming Interviews | Abhishek Kumar | Skillshare

Playback Speed

  • 0.5x
  • 1x (Normal)
  • 1.25x
  • 1.5x
  • 2x

Linked List data structures and algorithms for Programming Interviews

teacher avatar Abhishek Kumar, Computer Scientist at Adobe

Watch this class and thousands more

Get unlimited access to every class
Taught by industry leaders & working professionals
Topics include illustration, design, photography, and more

Watch this class and thousands more

Get unlimited access to every class
Taught by industry leaders & working professionals
Topics include illustration, design, photography, and more

Lessons in This Class

25 Lessons (5h 45m)
    • 1. LinkedList Intro

    • 2. Introduction to Linked Lists

    • 3. Insertion at beginning of List

    • 4. Print Elements of List

    • 5. Insertion at End of List

    • 6. Insertion at k-th position

    • 7. Reverse Linked List iteratively

    • 8. Reverse Linked List Recursively

    • 9. Detect Loop of Cycle in List | Floyd's Algorithm

    • 10. Find length of loop in Linked List

    • 11. Middle of Linked List

    • 12. Palindrome Linked List

    • 13. Find kth node from end in Linked List

    • 14. Find first element of Loop in Linked List

    • 15. Why Floyd's Loop Detection Algorithm works?

    • 16. Remove Loop From Linked List

    • 17. Check if Linked List is Palindrome

    • 18. Swap Nodes of a Linked List without copy

    • 19. Doubly Linked List - Introduction

    • 20. Odd Even Linked List

    • 21. Delete a node in Linked List (No Head pointer)

    • 22. Flatten a multi-level Doubly Linked List

    • 23. Remove LinkedList Elements based on values

    • 24. Reverse nodes in K-groups (Hard)

    • 25. Reorder Linked List

  • --
  • Beginner level
  • Intermediate level
  • Advanced level
  • All levels
  • Beg/Int level
  • Int/Adv level

Community Generated

The level is determined by a majority opinion of students who have reviewed this class. The teacher's recommendation is shown until at least 5 student responses are collected.





About This Class

Linked Lists are the a fundamental data structures and form a major component of questions in Programming Interviews at the major Software firms. This course tries to build the foundations of Linked List Data Structures starting with introduction the gradually diving deeper into it. Most part of the video lessons are geared towards explaining the problems and how to approach the solution, followed by implementation of the solution in C++ code.

So welcome to this course on Linked List Data Structures and Algorithms.

Meet Your Teacher

Teacher Profile Image

Abhishek Kumar

Computer Scientist at Adobe


Computer Scientist @Adobe

See full profile

Class Ratings

Expectations Met?
  • Exceeded!
  • Yes
  • Somewhat
  • Not really
Reviews Archive

In October 2018, we updated our review system to improve the way we collect feedback. Below are the reviews written before that update.

Why Join Skillshare?

Take award-winning Skillshare Original Classes

Each class has short lessons, hands-on projects

Your membership supports Skillshare teachers

Learn From Anywhere

Take classes on the go with the Skillshare app. Stream or download to watch on the plane, the subway, or wherever you learn best.


2. Introduction to Linked Lists: the difference in this, really, we're going to learn what the basics off link list. So link list easily. Nearly District two. So what does this mean? It means learned it ages story in a linear fashion. Not in a defensive second, it's known continues so for areas like the memory was located in a contiguous essence, so is it's an area off in teachers Onda First address it 100 dillaman for still guarantee that address 100 starting at 100 the side of Indian Food. Then the second address started when you Tofel. Then when you do it and so on. So the data He's a store continuously in the memory but in the link list. That is not the case, So link list is form from, Ah, list off Nords. So do your logs and these North Sir Lindholm on themselves. So suppose it's a linked list off in Peter's on. We have really won flee seven and ah oh Sue. If decision and just tended, then this may be anywhere in the memory like uh, 310 and Mr Nord. Maybe it says flavour 100. So these are not contiguous memory locations. And in the Nord we have one is better cost parties Daytona, actually detail that is stored. And the second part just stools. Bad rece off the next element. Next norm. So this was address under the second normal yet address 300 in. So this will store 300 then the next Deliverance he's started Just save under food. They're just six and or the next six. And this is usually court next next point. So it will restore the address of the next North in the list. And the first on the last Lord here there is no next North. So this is where the last element. So it went into No. So it can store here? No, Onda, we have the reference to the first nor which usually called, but here head north of the linked list. So in areas we can directly go to support 10th index and directly exes del Indio. But in the link list, we cannot directly roto some index me up a treat starting from the head Nord. So while it trading, we will be given the address off head. So if I'm asked what is the third element in the list, so I know that her did the first element. So I can keep the counter and see what's stored in the next off there. So 310. So we will go to the industry under 10. So is the second element. No. 500. The store there. So we will go toe just 500? No, we read the third element and we were the third element exposed the value seven. So this was the basic idea being linked. So as we compared against Aires, the non continues. And this is the main difference, Ondo. It has to be treated one after another. We cannot directly access particular, nor in the list. So thanks for watching in the next. Really? Well, we've seen what are the radios or prisons that we can perform on the link list. And then in the further sex, since we will see other types off linguist so by before to try just one point, like the next mold. We also have a concept off doubly linked list where we have not just the next element next north, but also the previous more so to read, resist one value and Bireun dresses. And then we have a concept off circular linguist. So, uh, we will see these in the coming radios. Thanks for what you 3. Insertion at beginning of List: reference in this, really, we're going to learn over the first off recent on link list that is inserting entertain toe the link list. So in the last video we saw at brief introduction off linked lists or it's composed off a Nord where the first part is data second parties, the pointer to the next North. So this was with the CIA structure off or linguist soup. So then the inserted a tussle to start with. I said that whenever we're given a link list, were given a reference studio first, nor which we call her North so earlier We don't have any no so her disappointing to me, so supportive and wants to insert. I want to insert five into a linguist off in two years. So first is to clear to node it kill you to denote Store five in their data six and and in the next six, and we will make it a point to the earlier heard. So it was pointing to new. So it's next to know and Mick, the head point to this newly created no jobs and no hair disappointing to fight, and it's next is pointing to No, I again want to insert suppose 10 No way will create an internal store. 10 here make its next point to the earlier nor noted Whatever her disappointing to make its next point to net aan den make this whole point to new legs. Richard Loeb. So after two in persons what we would get earlier, Ted her disappointing to tin tennis funding to and fire is pointing to No. So here you know that I am inserting Norden a big name. So that's why when I insert Nord in the beginning, the head has to be a virgin because here, disappointing to the first element. So know this the last element that were inserted in the first element. So we moved here from earlier it was going to Cleve. So we moved it to this new router and it's next going to are littered. We could have also inserted in the end. In that case, you know, you start from tired and I treat to learn and then put the north there, or keep another point of like haired, keep your friends too lost north and limited. In that case, ah, make the tail point to the new norm on the next off previous, nor we're into this norm. But by before, ah, we will do not being inserting the beginning. And these prisons are ordered one, because takes constant time, be cleared to mold and saying a few pointers. So what? Some order in order one or prison? No, let's look at this in a court briefly. So first thing we need to refine is the structure off No goes nor the the building local link list. So I returned according sleeplessness. First thing is neuter on the next use pointed in order itself. We call it next point. So the Nolde contents deter and another known pointer got a link list is nothing but the list of moves. So first nor stores point, truth and additional. And that in turn, will contained pointer off another nor between called next. So no, we need every to create nor really find a constructor number 84 to keep its next pointer. Two null pointers on next. Literally find an instructor with next pointers there next and third next. No, we need to define in certain prison. So first thing we need to have is a reference to haired. So if the area, and then we can start inserting nor into the list, for we have heard and miss a lean order ties there. So at this point in two nil don't be defined in sort of presents. I will call it in certain. So first step was to create a normal cool, more starting. Nor is a portal new notes Better so no, we have this. Nor next we have, uh, make its next point. Do here and then head point to this newly created new. So I headed up Bridget through this, Nor that was inserted. No beginning. No, Let's in third. Some later include Ah, let's in 3rd 1 and then insert men into three. So what should be the current state off link list? So first a inserted one. So after inserting one here, disappointing you to one and one is pointing to know next time, sort of in the beginning, who next off is one and had it updated triple similarly tree. So this would be the state off linguist Solar. It's very finder. My drink tingles so we have three north so head will be there. It's next will be there and it's next. Next will be there if I do next, next. Next again, we will reach toe no more to let sprint this and we're 3 to 1 as expected. So industry do is for the person off inserting in new Norman toe the link list in the further six cents mill. Is he? Ah, some moral persons that we can perform in the linguist. Thanks for watching. 4. Print Elements of List: conference. In this video, you will see how toe print the North's in the list. So when we're given a link list were given just reference to its head north. Okay, we have a list on the next off last normal vaginal, and we are given reference to heard that is the first North sort of bring the list began, create a norm and make it going to hurt. And while this is not Mel, so initially, we will see that it's normal. If it's not mill, then make in equal to it's next. So you should remember the structure of the North. Destructor had two elements First record later on the second record. Next point is appointed were nor this trip. So we will keep updating until it's not know whom soliciting no going toe to again. It's normal, so it will go here again normal, and while hydrating, we will also be printing here so very interesting data and move it food next, and this is conditional over and this Nordic Alterman so initially and it's pointing to heard so it will print one. So when it's printed and any leverage it to to you know and go toe to toe again and is not normal. So it will bring to on moving to three again. This is not Mel's so print tree on retreats. Next and it's next is model. So no, it will become no after printing three and this condition will not be satisfied and it will exit the loop. It will stop here, so it will print 12 and three all elements of the list. So let's see this in the court and we will be given the flesh to head on a separate day. Elements we will use when this a little to make it more visually correct. Okay, so it will keep printing the data and after the current next in learned it will learn arrow after the last element also. So I will heard Moliere's. Okay, so what, Leroy We were using manually printing it, so I will no use this superior to print the list. Okay. And let's see what difference. So, prince the same thing 3 to 1 that we were printing manually. So in this lecture we saw how toe friend elements of the list. So we have. So I train through all elements and keep printing them till we reach them. And so again, this will be order in complexity. Where n is the number of elements in the list? 5. Insertion at End of List: in our last victory. So insertion into a link list at the beginning of the list that every time we inserted in, you know the head nor was updated because had noticed the pointer to the first Norden the link list. So in this lecture, we're going to see how we can insert in New North and and off the linguists. So insistent at the beginning was order one pain show been reinserted front. It was one thing because we just created a new node and what overhead was pointing to earlier. So head was pointing to some Nord. We just maidenhead point this new Nord and it's next going toe whatever it was pointing to their literalist so it would cost in time of Britain. And no, we're inserting in the end full. We can do it in two ways. Either we keep reference toe a little, so we will have refreshed to hurt and reference to tell or second guess we don't have reference to Taylor were not allowed to keep another point of ortel. So if we have till then, it's again Order one. You know so good. Ah, this is our list, Mrs Our existing list here disappointing you until is pointing to the last Nube. And this is so for inserting a new norm. We will create in, you know, 400 years and we have referenced a tail. So this will the last norm. So we will move this. It's next point toe this new Nord Onda and this will become the tail nor so in this case, Head will not be deterred because her it is always pointing to first know that we're inserting in the end. So this again is order one pain, constant time. But it's we're not alone. Keep ISS separate refreshed until we just have heard aan den. If this is over existing list, then it will be order in time. In is the number of north in the list. No heard is pointing to the first node and we have doing third in the end. So what we will do, we will clear and you know, aan den. Once it's created for Lear, it will be warning to fight nil. So we will keep trading here so we can keep in current pointer or current more in and initialized to her note and keep moving next, next till next is no. So their next is present, so we will again move next. No, it's next seasonal, so we will stop here. So currently this in in this pointing to their so effectively it's way to find the last note. So now it's next Dismal. So well said, It's next to this new moon on we're done. So this off season will pick order and temporal everything. The insert in certain you know, we have waited through the whole list. So now we will see this in the court the last. So this way in certain at the beginning, in the last Knick terrorism, No, we will clear a separate function in, sir moved and And in one case, we will use the day Lord. And in second case, we will not use solar. It's initialize it till on and call it using tail. Who will also name this one de for using tail. So for straining toe, clear it in, you know, with the given. Ditto no dinner. Two cases once list would empty. So this will be the first time in order to inserted. So when listed, empty were boot heard until both are pointing to mull So this is the only time head will be updated point to this mold. I said that in that case it will never be a bitter. We go, we're inserting in there. But oh, in the base case, when there are no norms in the list, that time only had will be updated. So we need to add nerd kiss explicitly. So, yes, if it is known there No, this new normal Luton, there'd this will be known empty list case So it will not be a bridge in here. What will we do? So your door tales tell his finding to this law last North. So it's next will point to this norm. What if tale is no? It's next. We will not exist. So we I just need to add this case when tell adjusts or when Palin just had religious. So in their case Ah, till next sort going to this, you know? Okay. And in the end we will move this update. This tale also tell will point this last north. And this is the respect you off either the list, William your north So nuts or do Oh, So this Williams is in at the beginning. Let's come in. Tony's in certain corners end. I will insert same data 123 on And I can use the print list function that we defined earlier. So this will print. No. Let's see. So this was the case when we inserted in the beginning. Better very deter. In this case, it should be for staying, sir. Good one. The ninth Circuit. We learned then three. And so it should print 123 Comfort to treat one when inserting of the big names. So let's run it, Prince. 123 as expected. No, we really finally another function where we will not used the bill pointer Um e really keep it. Who will create a new norm? And in their kiss, this will be true, Will Here it is not this Make it a point to this on will not. But this condition again. And we need a new lord Current is equal to head so this current will be omitted. So if list with MTV of literalists and we're done if list is not empty while current is there, couldn't we will keep moving next andan So it's next nor digested. Then we will keep moving next. So in the last Nord, its next with north. Adjust on and we will get open this loop and we will make make the next off last norm or into this nor than this sort of work. I really loved this new forces and lets you work. Print So again it prints weren't toe three years expected. So in this case, we're not using till so every time the wait three door, the entire list. So this will be Worf one. This will be wolf. 6. Insertion at k-th position: in this video, we're going to see another in certain huge case for linguist. So we had seen holding certain Lord at the beginning of the linguist. And we're also seen or doing third North and then of the linked list. So in this case, or we will inserting more that Kate position. So if link list hatched supposed 10 north and I want to insert in order just for these and all, we will do that. So we are given a link list. So we have one head which we re pointing toe first. More for we have one more than two three food. I would over link listers. Currently four nodes and we want to insert here were given. Okay, Cool. Three. That means we have to insert their third reason, so even start over, come from one. So disease, First reason This is the conclusion that the start producing and this is for tradition. So we have to insert that third parties and on our date days Oh, I want to insert Pippi. So two people come here after two full. We will create an old first whenever we want to in 13 orb. First we need to have the Lord. So we will create a no on it should come here. So we will change this. So this No, no longer too will no longer 23 who will not goingto this No. 50. And it's next to foreign to three. So our new link list will be one and 50 will cover Tor Pless or, in general, let at Kate, please, and every other nor will be sifted by one person every other, nor bridges off other kids. So earlier we had four notes. Now we have five notes and in this case, had no did not think it was Our lives went into one, still pointing toe one. But there may be case when he's one cayes one mins I want to insert in order the beginning off the list. So in that case of you day 30 so it will be inserted here and it's next will point to one and the rest of the list. Norton on Dhere towards early years pointing here. So this will change and it will love one toe this newly inserted or business missile case when we weren't been sort at the beginning. Cayes one Onda there may be case like case more than actually whatever we have. So if gazed in, that is we want to insert 1/10 reason. Whatever list her Just four North's decision invalid case. And in this case, we will not do anything. We will return or you are free toe toward any Ramesses. So this is not possible. And and for 50 in the court, you can a June case greater than Joe because we're starting over corn from one first, 2nd 3rd for 10 to 1. True. So yes, use Let's turn equal to zero in this case is also not possible so we can simply returns. It's the leader like that or we can throw him. So let's see this in court. So lost video we have seen inserting a and off the linked list and beginning of the list. So let's write in new function here Ford a Cuisine K. So one thing is, we need a letter. The Nord actually and then we need a position which is K and no via one kiss were we inserted the beginning. Good Lord changes in other gives his irritable launching. So this is the case when Katie called toe one Swiss cage. One We need to create a norm with the given better on. And then it's next will point to heard. So its cage one. So this was over earlier. Head one was there. So we clear did and you know and it's next point to whatever heard was earlier for this special case. When K is equal to one so it's next is equal to head from all over examples we have taken. Ah, a global heard. So this is in order necessary. You can pass, heard inside the function itself like every in each of these funds. And you can bus reference to hard, pointed weird and in the cases were Oh, Head Norby can be changed. Then you need to pass the pointer took wanted to wear because we will be updating the head pointer in some cases, like printing the list, We don't need putting anything so we will just pass Heard star In other cases we need to cause nor the started started or terror We have taken our global aired for simplicity and our new head will become this newly inserted nor and then we don't need to processed further. We can return from the something If this is not because that means, um we're not inserting at the beginning. You can ordinarily smell case like cage list an equal DeNiro. Men simply return or throws a mirror. No. Well, what we will do you? Oh, yes, we have to insert. I get third reason. So we will keep a counter initialized to three and we will move to next note and I decrease our counter by one. So after reaching a to our country will be too. And we will move next hour comfortably won. So we will keep on decreasing the Contras. So it was Tell us now we have reached the desired prison and we sort inserted. Let's keep track off. We need to keep track of previous node and next Nord. So when we reached the point of insertion our previous nor will be here next normal beers. These polices are defined with respect to the new Norden artist creator. So this so we will make the next off previous I went to this nor and it's the next point to the next normal. So we need to keep friends to vote on these. Let's initialize both Baird wheels chambers. So we're next norm. We will move next. We will move next and whatever was the next, nor becomes the previous nor for next I tracing. So the previous noted a Bridget tow makes no whatever was next door in the previous case, our next more become It's next. So next he always one ordered or previous apart from this initialization. So whatever was next nor becomes previous note and then we update the next nor to its next in the same mattress in. So this will be one North aired off this previous mold on the new nor will come in between these two and then we need to decrease the count. Otherwise, this Lupin or terminate what is It's next, Nordea's northern there. So mind ur this, look execute. Still, we have current greater than one that is via when current becomes one. We know that we have reason there desired for Houston, but your current is greater than one. That means we need to move further. You need to move next, next, and every time we move one step ahead, we decrease the corn and in discuss next nor does not exist. That means Conte is still greater than one. What we have reached the last more because the next off large nordeste so currently still greater than one would be a reason. The last more so in this. This is the case when oh, this case like we have five North's and we're given the Ross to insert 1/10 reason. So we will keep decreasing the count we will reach here. Count will be six. So it is greater than one. But it's next is middle so there is known nor move further. So this is the wrong case in our case. So in this case, either you can throw some error or just return, we will not. That's the list. So is it does not enter this case. That means when this look terminates, can't has to even count really one and it will you tell also north t this case Now it has interest the last norm. So no career don't know and it's next will be next Norm and whatever would previous move. It's next to live with this current nor and we earned. There is no other kiss. I think we also don't need this case If Cage less than zero, then it will not be. It was Lord to it will not enter this loop at all than counties in case less than equal do do you know. And here also via explicitly ordered current is equal to one. So we don't need this. Take two. It should work for negative is hold. No, let's heard some lords to the list. So this is a list where we were inserting a dan. So one, then 23 So, after this position, the list is want to I mean so let's try inserting some marks, Schooler Insert then at first reason. No crying Pierre, second police. Um, no, we have five notes. So here we have 12 on the n word in surgery at first for Houston. Andi looks right. This after every answer since before the is here, then can take aim at the second reason from the list becomes Legace. No insure notes of 50. We have signal so we can insert at 50 reason No, we have six North's Okay, So stiff treasonous was takin toward Fort peace will come here and we will get most one step to the right. No, let's take one negative case. Also, let's I want to insert 70 and I give the police any it So still this fleece and we have Onley six notes on We're inserting at it so as forever cooled. This should not change the list at all, and it will remain like this on here. We will bring the list. Let's printed. It will come up like this. So it's 10 2010 20 12 51 to 53 so this works as expected. So this is all we insert in order at a given person in the link list. Well, this will had slightly more cases to handle and or earlier kisses will be just inserted at the beginning order. And because it includes both these cases, we can keep a cold one minute. Will workers as per inserting in the beginning or we can keep K is equal to one more than the current off number of elements in the list. Then it will work for inserting in there, and so this can serve Oh, or Lucas kisses. So thanks for watching 7. Reverse Linked List iteratively: who in this really oil be discussing? No, I read TV of ruling the reverse reversing off link list in the next video able also or give you socialism which will be recursive in nature. So I treated a bit simpler to understand. So first, let's start with it full. I have one link list. Let's say test four Nords on the last Norwood would be pointing to kneeled on the first nor will be but heard. Nor so our aim is there and there nothing. This whole process these so gory and we sort of get this or let me copy this. So these next pointers were changed after and heard should point to food. If we take any three notes at any point of time, we have one cool three. Yes, We take this window, you receive this renew so it may look very simple late Ah Guerra and and move its next Here been go to next North again. Do the same thing. Move its next here. Okay, I'm going next and form. So, uh so you exactly do the same thing? So let's initially let's start from this norm. We have a current node and let's keep previous Norm because we want toe set the next off current nor previous notes who we sort of have a reference to one previous North. So any cereal it's there is no nor before this one. So it will be and we initialize the current Nord with the flush nor had no job and also keep track off it Next node. So we'll do this. We will Do you know, the reversing a pointer here and move this in the next address and see will move here nor would move it next. We'll move here and previously will come here then current will go here and finally current will go here and in one step further we can move current here and then we'll see that Karen becomes nil, for we will stop there so we can write some pseudo court here so we can ah, start with Couldn't you would have started adhered or let's remove this in Texas. Just keep it simple guarantees here next physical currents next and because there previous his No. So this is the initial days. Then what we will do well couldn't for it'll be a well, it current more so then we don't have current. This will be our district via in the last tested we will have current trending this and previous well before and then heard so to be the previous So this we know No, let's fill in this. If current is valued, then what we'll do currents next to always point to previous here on full previous isn't a little friendly once next year Vignal like here. So we will right here. So this year I'm Richard. No, we need to move the pointers For once I have deterred this previously welcome here Current will move next and next to looking Move for the so we will move Previous is equal to whatever words current in the previous estate. Now it becomes the three previous no okay and current becomes next to whatever was the next north leg when who was the current norm in the previous stays? No becomes previous 33 becomes current and three words next in the previous north and we also need to move the next. It may be possible there next toward earlier this four So current has become food or current was food for the last Nord currently before and next criminal. So no off tear updating this current will move to know So it's next will not exist. So if next was there then of the next other ways we have returned, it will be able to terminate automatically. So suppose current is for I will for the lost or current is full concurrence Next is equal to previous so force next we re previous So you current is who previous will be three So this window here then previous becomes full So no previous is pointing to full and current difficult to next Next Widnall So current is no pointing here and next toe already Neil So this part will not execute Onda again This will take for current No current is for ending to kneel So it will come out of this loop and it will come here and it will set the hair to previous to previous is full so it wouldn't move this third pointed here and the earthen So let's write record for it. It's always good to write some coming worse link list and to make it more clear, I would write treated here and earlier We have been using this Ah Bullard Let's write some good quarter level so their head nor brittle head pointed will itself change soon. That's why I am crossing for in Turtle nor Point. So here it is itself a pointer on it will also it service will also change. So imposing Head Start start in the case of rent listed will not in We will just naturally we're passing your stuff and we can get rid of this all together we have a global nor let's write it in this way. So let's do some based checking like if we are given name valid Well, it pointers north. She's head. Is it cold milk winter or or Ooh, I would love to check the base case like if we have just one or like I am just one more and it's next is you know, And here it is here, in this case, we don't need to reverse anything after reversal wants next. Laws appoint to Nolan had will be here only so we can get rid of in this case also. So if it's next is null, then also we can skip because we don't need to reverse it. Toe mentored were in that case then we will return simply. And this isn't if this is not the case, that means we have more than one new works. Then we will very door core like previous insulate reversed inal current to first North and next to its next for real I treat ill current reaches here that is current becomes no So do we have current? We will look currents next to Quito previous and then previous becomes current Those we don't need. We have used the existing previous We can move previous ahead. Gordon will become next. And if next with normal that means his next her north already reached the end. So once this loop terminates, we will update there to point to the last North. Onda should work. Let's corn dysfunction. So we have one link list we had inserted in the last we do for this older link list and we will first print the original link list, then reversed a linguist and then looking So this was or his new list. Here you can see it's reversed three and then through p going to and then one don't 20 and 10 for correctly reverses the list. So little next really, we will see how to reverse the link list using recursive function 8. Reverse Linked List Recursively: in the last video we saw hold reworks a linguist attractively In this part we will see how true do it recursive Lee So that it is that you can split it into two parts like you have a function rivers and it takes heard north. So ultimately, this function will reverse all these nodes. Who all these pointers next pointers and also update this hurt 2.0, here for so we can see this problem recursive like Ah, I am calling this function 11 So one would inter Ah, in turn, call this function for its next Nords. So one is there and it sees this at another turn link list. So this entire thing is a link list on the parent called his own its first north, so we can see you test one Nord on remaining in minus one Orbs. Is this originally start and north? We can separate old one and call this reverse function on it said so we can move. So whatever heard was given to original function, we can move this head boots next for her did here and just called reverse on dysfunction. So this will internalise return correct list So what? We love food three and to And we will assume that this function has worked correctly and and given me a correct richer and moved there. There. So this is a redemption. So we have a function rewards and it will take heard. So what we said there Ah, we can Who will be saved? This point is first Nord in this variable and call the same function on the Father Lord So we can update her too Currents next. So we have moved there there and then call this fun salon this new word. So after this system, so after desist If be a June, there is this function works currently the remaining in minus one North Sea will be Indus A state for will be pointing toe 33 Really going into to two were pointing to fight no and head will be updated to point to this formal. So once we have this this part sorted or desportivo list what we need to do Whatever was a current note current we're storing current was during this one and now here it is finding toe to And then after this calling this rewards from sir on this sub list, it wouldn't be worse correctly and after their we need to or we need to keep track off to order was too full a missed one thing here. We also should keep next. Okay, so this next was to on head was too. Then recording this rewards for him and it reversed everything. And now what we need to do We need to set the next off people one and next off one do. Then we Ludin, because this function is done this much for three to and it's currently no her dizzy here, but the air saved one and two. So we will make twos next point to one. So this think will be gone and once next point to fight. And this is our rewards list so we can write the remaining part. So one situation, the worst you insert next next was to it's next will recurrent that is one on currents. Next will be no and we're damn near so you can dream and exclude scored here. So let's see it working how it will work Step was to so here and cut into his ears. And next year so earlier this function if it's corland this listing and then they will love it will call function a phone to three full. Why? After updating their So here it is no pointing here. So for this case, it will store the current pointer here and next pointer three. And it will again call this same function by moving here. Here, food will call on three. Who, colonel And for this case, head world here Current was three. Next was for and this again will call the same things in on food. And so I after moving the head the current year and next year. And you can take this as the base kiss so you can take their different er just one northern return. So this function will start returning from here so it will come back to its calling function. So there three will be current. So after this function returns, we just set next next is equal to current. So when this function returns here after updating this part So in the stack off this function called current Wall Street next was for so next Next is couldn't and currents next reasonable. So what? This will do discipline. So this function return four. So this function under done this And here we will say, for with the next here we restore mixed. As for so it's next will be current. So it's next Is current here currently three and then currents Next his metal this really only one pointers. So this point, there was no inserts going So this is the list there this function gold returns. So this function call once it return here you to change the state off the sub list three and four. So here it will see next is three and current is too. So once this function returns, it will take this list as cities as returned by the previous stooge. And it's next was a little so no, it will do next, next to call to current. So next was three threes. Next will be current that is to and currents next with renal darkness. This so this is no the state off the published 234 and it returns here. So in this stick, next is to and currently is one the next next to recurrent. So who's next will be current, that is one Whoa, it will no be one and once next really know. So this is the ultimately the state of the list during this sort school, which is the correct one because there does no move before, which is pointing to treat then two, then one journal Earlier, it was 1234 and head over there. Who this is correctly, it was the link list. So this is a recursive implement isn't let's write it in the cool. So in the last video, we had Ryken the treaty very. Let's write very personally so I can copy this base case. If there is only one node, then we don't need to do anything. So we started by first Northern separate or the next lady running. And we also need to move the head on call dysfunction on the new heard and after it urged DeVos Dark sub list within off. Dude. Okay, Forward Pechiney chairs on this stood work, so it's just 45 lanes of cored. But to understand it, it needed Sure, once explain, isn't Let's see if it works full weapon coming toward this. So we have commented, or this reversing course who rented the least choice and use the recursive definition. Okay, So this has correctly reversed the list three, then 50 to 1 2010 And so this is all we do a recursive implementation off reversing a link list. The court is much more simpler, but it needs good understanding off how rickerson works. So keep practicing problems like this and you're being tracked for drinking and in questions latelys. Thanks for watching. 9. Detect Loop of Cycle in List | Floyd's Algorithm: in this one. We're going to see auto Detect Lupin a link list or in other words, hold detect If the linguistics I click. So in the first example, you see that when we I treat through this list, we will come here. One, then two, three food. So you using? The next pointers will be there next pointers and this is data and we keep on going to next North. And after this last North, the next seasonal to be rich. The end of the list and the actress and process terminates. But for the second case. So this is not cycling, there is no. But in the second example, if you move from one toe I moved from one toe to toe and its next three and then four, then flavor. And the next off leave is miss to for we again return. So we keep on tracking the next Lord and we reached to again. We moved to treat and four five and again it's next is too. So it will never terminate because there is a look in this link list. So there is look, so how can we find this loop? So, uh, there are if you is, one simple approach will be toe. Keep track off the North's that we have already registered. So is the investor people mark one as we stirred than 2345 markets known twisted as me, ah Ri's Dan Loeb and after four baby again, so received her who is already marked re stirred. So we will say that we are Easton or not. We already Western and it has a look. So this would be very so our litters, Netta and next pointer So we can additionally keep a 1,000,000,000 re stirred which really very before it falls. And as we traverse it, we will market true. But this would involve changing the destructor itself the structure of the northern itself . So it's northern. Oh, that much recommended and it would be very trivial solution. So I can be too use a passing for we keep Yes, you keep it has map and ah for lurid will be empty on. We forced to start with northern one and we will insert northern one and Margaret Cruel. Then you will insert again. And similarly for 34 and flee. And when we read it in, you know we take If the North exists in the house or north. So when does not exist, it'll be inserted Nord one. Then we will go toe to toe does not exist in the house of inserted. So we're a little five then after five after Fabi again reached two and we check if to a guest in the House of Lords who is already there. So we will say that Luke is there. And don't be a towards solution which was given way. You're saying just named sword forward This algorithm say is there keep two pointers one first and once Lou earned Ah move this first pointer by one step and this slow pointer by two steps Each time or so you move this screw pointer lay one step turned loose First point await news to use this first So it has to go first. So support We have a loop off canards through the loop Baluch Conceptual! Yorke's so in this case, this loop Hood four knocks 234523452345 Descends for nerds! So when? After one step So first time it Anders balloon support slow pointer! Is that plus 20 year and slow pointer is some aerials than the first time it enters the loop. So it has a different off some difference. Say, did you get off in Lourdes between Did so after one stupid first moved away for your force Troyer UNIX if earn slew order index Well, yes, So after one stupid will be are useless Cool on this movie are useless one. So if earlier this gap waas in no discover becomes in this one. What? Once it completes this no, it will come back. So if if this look has and logs this is ah, hair to buy in north been, uh so So if you in this loop you see that if you go in this direction you can see that this ah Nord fastest ahead bay in Lourdes. But if you see the other way, like fastest changing this lunar, then this will be in minus Then first will be legging real menace and logs. So after one step, this leg will decrease because faster move to step in and slower mood wants to. So this will become in Linus and minus one, and this difference will keep on decreasing and ultimately it will reach zero and this fast normal. Ultimately it's up the slow nerds on them afters somewhere treatments. So when so in the beginning we heard slow and fast pointing to head. So after some time, while looping through this ah cycle after some time these two will meet again. And when they meet again, we will say that this oh link list has Luke. If this link Liston nor any loop, then the first normal reach I learned and slow below what he's done for whenever we reach no, we will say that there is no look. So we will terminate their itself, saying that there is no and we've been well, they meet again, some there. Then we will say that this linguist has look so no, let's call this idea so first. So I will use the maps Allyson has meant. So let's create and function. So it will take you pointed to the head on. Really take a map on ordered myth which would reappear off Lord pointer on bullion sing whether it has invested or not, we can also do this. It's simply sit so certainly green easily empty. And as we travelers we will keep inserting the North Desert. Would this map a little to look? Take the current nor weird. So we will barriers to travels the least and see if the North is presenting the map or not . Because we insert the note on leaving revisit the No. Three for its present in the map. We will return group Mr or Lonely Toe to. Then we will return. True. So if it does not enter this countries and that means it was not Richard and then we will insert for her. Normally the key and the small is Look, Mr London, who currently sits next, and this Luke will terminate when it resulted in. So if you treated, then we know that that it was no for your return falls on the At this point, we have a linguist, which is more cyclic. So this is the link list. We need to insert a second in order to check our record. So what? We're Louisville Move this next off. 32 began. Say that the next off trees 20. Then there will be little let's write function toe. So again we were travel, so list. So we want to just stop on the last norm. So when we were the second last note, it's next is there When we reach the last note, seven current becomes equal toe this three then it's next is not exist, so it will come out of there. No earned and current will video Last nor full. We can certain its next to re Second Lord. Let's hurts next. Okay, and now if we know we need to very further, this list has become so I click. Let's try to print this look. This list is will never turn it so it will print. And 21 to 53. And then again, 21 to 53 again, 21 to 53. Let's run disabled quickly terminated the program. Other Were you to ah, take all this area so we could clear in stop so I started it. So So you can see that earlier This world The list notes 10 21 to 53. Then again, 21 two for victory and so on. It gives looking through that list So our list is no. So I click. So let's not bring this list. Onda call over function to detect Luke for before creating the look different has Lu on and after creating the look again food Prince dear or live Jiro Means falls. No, it should print in the string. Former You. So the first time we detect the look, it has no look for returns Falls. Then we heard the Lucas and then again print, and it says that he is very low. So it is with the first mentored. Let's create a second matter. Oh, never discussed fluids algorithm. We'll take two pointers on first water initialized to heard Andi was We'll make sure that the winters are Willard and first were increasing by two steps. First, Next. Next. So you're fast Not next to dismal. Then calling Next under will cross the program, so we need toe check. It's next to the older present on demand for this movie. Wait two steps. Andi, check the flu. Tickle toe first in return. True. Go to turn blue This loop either permanent when it returns from here. Then in this case, this function will return on the other cases there. This is not cycling. Um, this slew on first from this first reaches burned off the list so In that case, no return force alerts. Try this. Let's herder line between these. So here we detect Luke way first emitted, then print it. Then Detective way Second mattered for its algorithm and printed. Then we insert the loop Inert list and then ah, huge Votomatics to print. So it's a different hair. Falls, falls Bendis line Then after loop is inserted Edited Print True, True for alleged Tickner. So that expected Prince four souls than true true. 10. Find length of loop in Linked List: in this video, we will see how to calm the number off. Nords is very loop in a link list. So in the last video is for the florid seliger them and a couple of more algorithms to detect. Look in a link list. It's a link list, uh, loops within itself like the next off favors to the normal English tweed or blue Here, the last Children terminate its next to a liminal. So this is the case where there is no look and this is the case. Were very, you know, So in the last Really? So how we can detect the loop for We heard one slow pointer on one first pointer bought initialized to heard. And then we were moving the first pointer by two steps and slow pointed away one step and eventually the first pointer will catch the slope went to somewhere. And if they meet again, then we will say that there you So in this case, we will also come. The number off elements in the loop is the count. We have 12 three and 44 elements are in the Loop Buder school three food fleeing. So these four Childrens are present in the loop and we heard some here one. So this concert return for in this case, so we will see how we can do there. So, Noah, once the slow and five point on me here after looking through this loop a couple of times are a couple of times or more. See these two pointers meet here and here We were saying that there's a loop present and we were just exiting the court. So know what we'll do. We will keep this slow pointer fix too. We don't need the first point or anyone. So we will get rid over and we will start treating the list like resource earlier. So we will insulation or to this Nord wherever this ruined first appointment. So nobody know that slow Quentin is inside the loop? No, what we will do I will keep increasing this next nor this moored that we initialized to slow Nord. But we will keep this loner fixed. So this new orbital go here then Then it will come here veneers and finally it will come here again and no Well, see that the Mord and Slow nor our displays on After reaching address and we will incriminate the corn. So, like we can initially the company road and glared Here come really come one Or really any celebrities? One brother. Because this is the first Children, then two, then incomes. Here gone, Drillbit three will next. It will before. And now if I go next, I see that I have come back to the starting position that the police in very this go knowledge. So we will return that the countries who so we'll just mortified of through its algorithm that we used in the last look to so here. So there we were returning to. So instead let me create its function to Condon, or so initially, the corn to one and create a new temporary norm on Denise alleged to this mode. So they're really passing this loan or the point slow. It's returning in so I can print it here. So no boot, this current node and this normal that is slow. Naled are pointing to the same place who well, it's next is not equal to this Lord. We will keep moving next and incriminating to corn. So this bring the number of New York's let's straightness for we can comment or BuSpar We'll just use the fluids method of detecting the loop. So here it will. Sprint falls because there will no look. And this I had added inside the loop case only Herzer print false than this line. Then we inserted a little blue that we saw in the last Will you on here After the loop is inserted, its footprint We'll fly. It should bring flight. Let's see. Yes, we just giron when they know true and false Who so no look. Then Luke, inserted on the current is five on its true 11. Middle of Linked List: in this, really? We're going to see how to find the middle element off given link list and bring that element. So, uh, you can see we have link list with six elements and under one can say that these are the middle elements because since we are even number of elements here, this exactly Duterte's, there is no element exactly in the middle. If the AARP level men still five only than to your villa Merry little men. So what of these are valid middle elements? So in this case, it should print three or four as but over Different isn't. And if it's ord, if it was 1 to 5, then it should have been to a tree. So let's see how we can do that. So we're seeing a hard to find or looping link list. There were used to pointers once lost, which was advancing way two steps in every attrition and there was a slow pointer which was attracting are wanting me one step, so we will use some similar concept here. So let's initialized two pointers, one first and one slow, and we will assume that the list has no loops, so this is over Dems. So after next, step slow build here and first we're been in the next step cost will be here and slowly here. Then first will come become so in second steps global beer and then finally slogan Come here when first becomes model so it will print for It's very simple. On the other hand, if feared revered or number of elements been, let's see Louise here and first border initialized to her pointer after one step first will come here and slow been come here in the next step Slow will come to a tree and first will come through for you and no over condition is that we make First is equal to closed Next next Fuji end of the loop. We never here First North next should exist other ways. Uh, if this does not exist, then there. There's no point in calling its next because this itself does not exist. So are conditionally there. The next off first pointers, who'd a guessed on also the Slope Winters flow pointer will definitely just because firstly already moving ahead of that so far, so they just and it's next to the biggest, then only we can find next. We cannot find next off a normal so far start next should be a value Quinter. So here, received there. Forest agrees to the end and there is no next no. So we will stop here. So again, uh, whatever. Slow pointers finding two people print in there. Similarly, for this case, also, we had printed this four, So there are going to be four, and there are three. So let's er rate a quick word for that. So we will initialize two pointers or pointing to heard and the conditions would be their first nor devalued and fasts. Next. It'll develop. We will do fast next. Next on Slow, Be alert. Once made one step. And when this breaks out off Luke, we know that first has released through the end of the list. So we will. Friend worked over slow pointers warranting toe Moller Run the school. Oh, it's coming toward these things. Let's first bring the list to see what? How long is our list? So list had six elements, so it will bring the four Children that is to so here it has printed toe. No, let's get rid off last element. So that we have or limp list. Let's get rid off D or three. The last Children's who or Ah, little off. So it will be 10. 21 23 And now it should. So now it prints one because one is in the middle, two elements are left off. It will insert the right off. 12. Palindrome Linked List: In this problem, we're given a singly linked list and we are particular whether the LinkedList, the nodes represented where the LinkedList form a palindrome or not. So in the case of a palindrome, all the numbers, if you read from left to right, It should come to me. Seem, for example, in this case we have 1, 2, 1. So you compare the first and last, they are same. So again in second-last, same. So whether you read from this side or this side, it will be Sim, 1, 2, 2, 1. Now read from the seat. It can be even lend, it can be Orland. And you are given, of course, in the case of singly linked list, as usual, you will be given just the pointer to the first node, which is called head node. So we have to return whether this is a palindrome or not, so true or false. Now, let's see how we can do it. So let's say we have a linked list, 1, 2, 3, 4. Or let's take a palindrome. So let's make it two, and let's make it one. So this is a palindrome. So what we can do if we are given a LinkedList, how to compare if it's a palindrome or not. So depending on whether it's odd or even. So if it's even, then the medieval world line here between two numbers. So this half in this Jackson should be same as this half in the other direction or the other way around in this direction. And if it's Orland, for example, 12321. In this case, again, whether we read from left to right or right to left, it should be seen. So this central one does not make a difference. It can be any value because it will lie in the middle, whether you read from left to right or right to left. Let's write it from right to left. So one is the last element, so it will come first, then two, then three, then two, then one. For middle one remains same. So it's irrelevant. We'd never compare the middle element. So there are two cases already been. So let's see how we can do it. How can we compare first and last? It's not very simple. It's not a vector or any other data structure. It's a LinkedList for fetching any value we have to iterate just in one direction. You cannot go back. So the idea here is that we have to compare first half and second half. Left part, right part. And the direction of comparison for left and right should be opposite. Because we are comparing first against last, then second against second-class. So in left part we are moving from left to right. In the right part we are moving from right to left, or vice versa. Both will work. So you compare the first, the middle elements, the mid two elements, and they are same, then next one and so on. So what we will do if we have two pointers, one pointer or the first element and one pointer at the first element of second half, then we cannot compare. This. Competition is not allowed. If we're moving from left to right in the right-half, we have to move from right to left in the left up. So you can see an idea that we can reverse the first part. So it was the first part, then we will have to 1 and the right part leave it as it is to one. Now we can have two pointers pointing to the first element of reverse, left part and non reversed right part. And now just increase both the pointers one by one and keep comparing. And at any point of time, if the values mismatch, you return false. And if you do not encounter such a situation and you reach the end of the list, you return to. Only thing is that while writing the code, you should take care of this scenario or the uneven. I'll tweet is very simple. If you know how to reverse a LinkedList, it should be very easy for you. So the idea is that if we have a LinkedList, ABCD, and we have to reverse it, we keep one current element and one previous. Previous is initially pointing to null. Current is pointing to head, and the next is pointing here. So what we do in a loop, while we reach the end of the list, we make currents next, two previous. So whatever is the current, its next pointer, now pointing to here and this is gone. And then after doing this, be moved previous here, current here, and next year again. So previous is current guarantees and next, and next is its next. And we keep on doing this. And again we will do the same thing. Currents next is Previous. So next job B will be a. And then again we will move all these pointers to the rate. And finally, b will point to C, C to D, and there will be nothing left. So next we'll become null. So this is how we reverse the LinkedList and I am following the iterative awesome. You can also look into recursive was an attribute. So once you are familiar with this part, so this is the main part that we'll do and we'll do it for the first half only. And you know, the reason why. And only one special case would be taken for even an Orland. So let's write the code. We will see here an example of uneven. So first let's take an example of even. So we have 1, 2, 2, 1. And of course it's mixed in. So how can we reverse the first part? So you remember the notion of slow and fast pointers. So slow pointer we increase very one-step, fast way to step. So then fast reaches the end. Solute will win the middle, plus or minus one depending on art. And even. So we will have two pointers. Pointing to head. First pointing to head. And here you see the most enough current and previous. We have to reverse the first half. So previous as usual, let's keep here pointing to null current. Let's keep here at the first element. No. We follow the same thing this loop. So you can add a base case if head is null or hertz next is null, that is just one element or irrelevant, then return to. So let's forget the base case and come to a generic case. So we will have a loop after initializing these four pointers. Whale, fast and fast next, both are valid. Then the run this loop of reversing it. So when we are, it's negative will become null. First reaches either here or here. In that case, Slovenia window somewhere in the middle. So we would have reversed half of the list by that team. And we can stop there. And then we can do the comparison. So current is equal to 2, slew. It's already slow for the first, address them, but we are writing a generic cool. Slow is slow next. Our first will be fast. Next Next. And currents next will be previous. This is where we are doing the reversal. And then previous takes the value of whatever it was. Current was there. So DCL we do. And this will stop depending on are the ribbon. So let's run through it. So these are here, all slow, fast and current at one, then fast and it's next are valid. So we do current is here. And the first. And then slow becomes comes here, fluid. Now pointing to two, fastest, pointing to its next next Daddy's here. Here are the 2 second to here. And then current's next is previous. So this is one. And previous CMS where current was. So this is the state. So one is here, it's next is null. Then we have to do one fine ordinal. So this part is same, That's again part. And previous is pointing to one. Fast, disappointing to second to slowest planting too. So again, fastest valued, it's next is valid. So this loop will execute again. So current comes here and the slope flow moves here. Fast. Most weight two steps. So now fast is null. So clearly this Lubalin after this processing and currents next is Previous. So next of two is one. So let me rewrite it to it's negative one. It's next is null. And previous will point to the second two and no end. So now we have two linked lists and we have to compare starting from first for both. Sorry, p will point to the first two. This current was pointing to, forced to, or it should be seated. So a previous is here and slow will read here because we are one slow way, one step. So now we will compare both P and S. So P dot value Sylvie, same as S naught value S is slow. And then be equal to p next is equal to S Next. And at any point of time, if this is not equal, we return false. And when this loop ends, that is, then P or S becomes null. Then we exit out of this loop. And then we return to know for order case what is the extra candy some needed. So again, the same code. Stick one to three to one, so far as to slow and current. All three here. Previous is pointing to null. So all three are valid. So we make this point to null. Flow comes here, first, comes here, previous comes here. Again fast and it's next is valid. So we run through this loop that is current becomes slow. So current is to null. And then what we do, slow and fast, increment, slew fast. And then current's next is previous. So this too is now pointing to one. This is one. And then previous his current. So no previous is pointing to this too. And now this loop will not continue since it's next is null next door fast. So it stops here. So what is the state? We have to 1 then empty. So remember that if we have odd number of elements, we don't compare the middle one. It does not make a difference. This middle element that gives me a one to three to one. Any value can be no middle, so no need to compare it. So this part is fine. And previous now is binding to this, to the head of this one. The same was the case when we had our number of nodes previous was pointing to the head of reversed list. But they're the slowest pointing to the first node of second half of LinkedList. But here that is not the case, slowest pointing one element before it. So in this case, we will add if F. So in the case of evenly and if you did become null, you see here. But in the case of Orland. F is valid, it's next is null. So if f is there at the end of this loop, then we know that it's odd length. So in this case, yes equal to S naught next. So this is just one extra line needs that needs to be added for our keys and then it should work for all the cases. So this part was tricky so that you don't miss out on some cases. Now let's write the code for this. Hope you understood it well. If not, pause the video and do a few exercises yourself, take a few examples, run through this. Now let's write the code for this. So this is the problem. First, we will write the C plus plus code. So again, add a base case if you want. Although it's handled in our genetic code itself. Then we will have a few ListNode pointers. Slew equal to head. Fast is equal to current. Or you can write seawater to make it more clear. And previous, I'm writing short form. It's not a good practice to just keep it fast and simple. Now. While fast and fast. Next, mode pointers are valid. Current equal to slew, slew equal to flu. Next. And fast, fast. Next. Next. And currents next. Previous and previous equal to current. I forgot to mention the time complexity. So clearly you see that we read through this list left to right, and we stop in the middle, then feisty creatures to them. So we have taken o of n time here. And then we again compare those left and right parts. So again, often roughly you can see we compare the left and right parts one-by-one. And optionally you can reverse it back also if you want to restore the list to original state. So overall time it will be o of n and a space or one, since we're modifying the list itself, a simpler way would be to, if you're allowed to use this piece, you can keep a stack, just a drip through this list and keep all elements into the stack one by one. So the last one would be on the top, second, last, and the second, and then keep popping. And again, I tried to. This list and keep comparing it. So that will also work, but that will require extra space. Now let's complete our code. And we needed one extra line for that or gland case. So if f, What we will do, slew flew next. And then we have post hoc reversed, second half reversed. Previous is pointing to the head of first half. Slowest pointing to the head of second half. P and p equal to S. Well, and if this condition fails beforehand, and you do this again part, if it fails due to phosphorylate, that means we have reached until the end and we did not find this inequality. So you have to just return, check whether P is null or not. And the solid and accepted. The same thing you can do in Java and Python. Not much changes required if you get the idea clear, it should be very simple to convert from one to other. Okay, so the mistake is here, martin, these things. If B's none, then we return to wrongly written not equal to null. Now the same thing we can write in my tomato and accepted and also accepted. 13. Find kth node from end in Linked List: today we're going to see how to find Kate Element from the end of the list. So finding it from the beginning would be very to be like If I want to find third Element, I will start from aired and keep a counter. It will be one here then, as I go toe to little inclement contract to and as we go to three over Congress Tree and it matches the games we print there. If we warn an element from the end of the list Ah, then ah, you need something because these arose. The next pointers are on Lee go in the forward direction in the case of singly link list. So one way would be like, ah, close to your burden, Conde elements who just don't elements and support there are in elements in the list. So in this case, six. And let's say we have to print 2nd 1 from the end. So second would do 1st 2nd So we can just This will pick one night reason. And once we have retreated to relinquish too, we will do and winnitzki thankless one So we can next time start again from there and keep increasing So So this problem Lookem simmers printing in minus K plus one entitlement from the beginning. So this would be one mentored second, we will be there straight of it. We keep two pointers and we know that we have to drink Kate element from the end. And so we will advance one of these pointers. So their difference would just little difference between these two is at the moment. Deal for began increase. Move one of these pointers by case steps like if we have food in, we will and due to their to her name initially, if they move and my case steps, that is Keyser so and when you there and preserve their difference between these two. Is two the police A murder? Well, just many differences. So no, even it's moving and two years. So first remove it by case steps. Then, after we removed by case tips, the inclement, both of those both of the North Berry. One step. So next in one will be here and to hear who misses hanging over your increasing the first time steps that condemns to third time's too, and then and one becomes four and who becomes six and next. And who comes here and and when comes here and now we see that into is no So we really stop to this position on this slow pointer will give mean the Nord we're interested in so one and two. So Kay was too. So this is a very neat trick. Just advise the first point of I kissed if beforehand and then moved them both at the same spirit. So when the no no that was leading just the crosses there and then the legging pointer. We're going to the globe. So let's cord this bring cared from and And we need to hurt Pointer. And we also need a look. Okay, for real initialized to Lourdes and ah, when he's greater than you know what we will do little detriment. Okay? And also But it may be possible that the linguist has a three elements and we are requesting it to print 50 Children from there and ridges north possible so we can urge And it's not check here that if lead Nord is present User Villiard then only do this ends You're inside this way Loader This case greater than you. So is religion and you know, But the lead Nord has released to the end of the list that is leading order has become normal. So in this case, we can. There you have requested a Burnham keys that loves there's been and we will return from here whether we will keep making lead going into next. Once care has become digital. Oh, no, We need toward the Pointers by one step till lead becomes no Mead leader quartile. It's next. And when leader comes, Nell's leg will be the pointer that we're interested in. So let's just to this scored first, see, what is the list? So we have this list wolf Six elements through looks Parenteau Thurday. Learn from there. So for Deliverance is 23 is the 1st 1 host second prince correctly in four Children. Support for everyone. Yes, wouldn't 34 Let's give it a big number. More than six for correctly prince or nutcase larger than the length of the linguist will be lentil interested six. And we are asking you to print every new riches more than its land 14. Find first element of Loop in Linked List: in earlier videos, we have seen our to find looking a link list. And one of the algorithms we used was Florence Lucca talks an algorithm, find a fluke against in a link list or not in this oh video, we will go one step ahead, and we will also find out what it does starting off the look or the first element of the look. So, for example, in this case, we start reversing from there and who is part of the look? One is not part of the loop next to learn this too. And it is part of the loop. So we have to find the first element. So we will use again floors look, prediction algorithm only we will just mortified that a little bit. So remember, ing off Lords Luke Dixon. Ah Oh, the slow and first pointers meet at some point so literally on that a room this so after one step slower will be here next step. Similarly, after first step first will be here and second step last year. Now in the third step, first will be six and then to on a slew reared for makes a step slow here. Cleve first Weird for next step first. Really weird. Six and slowly we're six. So this slow and fast pointers meteor? No, what we have to do. We have to keep one of the pointers here and mother littered. So let's keep first point career and moves slow. So slow is no Quentin too Head. Once we detected the look. This is the place where they met. So no move slowly here. Keep first to No, we will increments both of foreigners by a one step. So what? Lou Mm. Bullard's look detection. Vince Lewin First for interest, Meat. What we do we will. The same slope winter do heard earn. But we will not change the first pointer. No, Wales flu is not equal to first for the place where they meet. They will meet again. Will be the starting on the North. No, we'll just print slowdown date or Busan matter. You can print 500 ties. So So now from once to meet I am works low point career and first easier for a well earned one sport off these by one step. Well, you might want seen both way ones too. So before detecting the look, I would add one thing. First way to step on, Throwaway. One step we're once did me. We are inclement both off. The very one step. So slow moves here and first comes here. Who it has in this case, it I met in the step only. But let's look at some other jump in so that it's more clear. And let's say seven. Next is four no wagen drum owned algorithm. Louise close to you in the next step. First will come here. Earn slow will come. Yeah, the next steps. Who is there? First year flame Next step first we were seven. Slowly, we're for the next to Louise slave and fastest. It moves to seven. Then again played So the muted this slow and first wonders me too. No, I'm the slow pointer here to the beginning. No flu is research. Could this and first remains here and started incriminating ones too. So six and slow. Most ripple, then seven. Almost 23 don't force until moves to fool. So they meet again. Hair it for And this or the beginning of the group. So this is Gillard. Um that is used to detect the first element. Find the first element in the loop. So let's write accord. For that. I will explain how wide this algorithm works in more detail in next will you? It will take some time to understand why. Why this algorithm works. So I will create a separate redo for their No, no, Let's scored this thing. Fine lightning. So the initial part of the court will be same as ever. Detection algorithm. We have slow pointer any Celeste to her. Then we have another cost for internationalized to head. We can hurt some quick ticks. Lake, if it is no longer hurts. Next is null return and that's not record. We're doing excellently. We can always there these six So what's lose their trusted there and fast next is there so that I explain earlier We need to check for the next off first also because we will be using frost next and also incriminating. That's with last next is null. Then we just be going finding its next. Then it will. The village gets even dis involvement decisional pointer and we're tryingto excellent. So no, Vince, when first meet, we can record of this. But ah, when it breaks out of this world. Look, it's either because they met somewhere in the case where their water eggs actually loop in the list. Or there may be that there was no loop on the first point of reach there. And then we Oh, broke out of this. Why? Look, so we need to take Ah, yes, Lou is not equal to first. This will be the case. Were no loop exists. Don't. We can print No. And we will also return because we need don't need to process further there, you know? No, this was the case here. No, lo Cajuste. No. And just so that it's logical to first for what we have to do. We have been insulated one of the point just to hurt on again. Run this Look who is slow. Not equal to fast. So they have moved global head and I realize the votes will and fleshly ones too. Onda, you're very certain and they will meet again because we have already take that look adjusts in the list. And so according to Florida algorithm, it will be again at the beginning of the look. So know this Louisville on Internet and slow is equal to first. And in that case, we can go ahead and print What is the value off the north? And there's who currently. So we should comment or discord first. Let's to court is the link list. So this is the link list here. So this has no look. So if we just to run point Luke beginning on this list, let's see to it renders more. Okay. So for her development, it's next in winter. Oh, I have given a wrong condition. You should be north of this. No, let's around again. So it could a cliff prints. There is no look. No, we will enable this loop. Create. Look on what we have done in the loo we hadn't made Oh, current Izard currents. Next. This is the end of the loop, linguist and made its next one to second. So the No. Three is pointing toe 2020 is the beginning of the look. So now again, if we run this, it should sprint 20 because we're under this loop. So the first loop element instantly. So it correctly prints this. So this was a very useful algorithm and we want to find what is the first element of the We can additionally modified this also to remove the look 15. Why Floyd's Loop Detection Algorithm works?: in this, Really? We're going to see the validity off Lords Luke detection algorithm. So in earlier classes we saw that so we can find or the first element off loop in English too. In this case, forest off first element of the link list because you start reversing from the beginning on the list. And this is the first element which is part of the loop. So we solder ah, algorithm works like if you start from head and pick two pointers, one first pointer, which most way to step on one slow pointed there mostly wants to. Then somewhere is the meat again. Then we say that there's a look in the list food. Let's say initially, the meter nine. Who mine is toe Norden were slow in size pointers, meat. No, we need to find the first element of the look. So what we do, we keep 1.2 here at the place where they met and one point to the first node and no boat will advance. Weighed one step and they were looking me hurtful, the starting point. But we did not see why this elevator work. So we will see in this video so no. Or let's do a dis linguist into a few parts cigarettes, for this is the first part from the beginning off the list. Didn't this do you know it reaches the first note of the mist? Basically, it will mean 123 That is how our many steps we need to take to reach this node. So let's say this is number of a steps idiom. What I will say distance, distances. Another thing is the length of the loop. So let's say the length of the Lucas. They didn't know what of norms or the number of pages so disadvantage in in this case, it will be one toe three, one, 234567 and eight. When discussing what the current is not require Nick and is the number of elements in the loop. No. Another part would be from the this nor the first North of the list. Lapointe. We're slow and fast. Pointers met for the first time. Let's send and distances do. No, let's do some quick killed. Listen here, So, no, let's do some calculations. So let's say the distance trip early force point. This is the distance from here nor till this point they're starting from 1357 and phone flying. Finding the distance Still name for clarity of great main Here the distance moved away. First point will be this in distance. Nous before meeting may be the first point of has taken a few wrongs air on this loop. So some question times this and in is the length of the look. So it trees the four and took some rounds over this loop and then finally to case tips to retail at Maine Andan. So Veered key Similarly, distance moved by slow pointer. It'll reach main is the same distance him and lets it also took some runs on blue. So this one, we're different. In most cases, I would say it will be one only so see to win Plus again. Okay, so this wonder also reached four. So we added, um then took a few wrongs on this loop, then again reached for so the situation and then care distance to reach nine. But we know that this force pointer dextrose toe every time and this sticks wants to. So the meat after sometimes you in there time This first point had covered twice. The distance is the distance of slow pointers, so we know that. Do you see it two times Deuce. So you know, we can substitute the value of India. Sandia's So do you see every times m plus see one in plus can just two times ds and be assistant differently. This is him. Less list. Okay, No, we can take the same gales even in tow. This served food will be here on this earth and two in minus image. You know, similarly, to give in this case, kid. Plus to three to minus soon. Or we can say M plus key is a quarto. See? One minus 232 and no diss term is a constant, so you can replace it. See? Common question. So Well, here's 1/4. See, Time's in some constant times and still missing or no, let me corporatist milligram. For that we can see together with the Christian. So this is over, Christian. That really rib m plus Q is he tamed him so we can all terrain to this image. Acquittal See, in Linus que I just give you a great inside. So this is our m wanted them. No, no. Look at the second step, Natalie. Once slow and first winter make that name. No, there's a point or people at the beginning. And we two at the point where the mitt and no boot ordered one seem very one step. Border equals street grinders. So we're claiming their devil meter food. No, we have received way. Slogan even reaches here. So let's it even reaches here. So how much distance it will cover? It will cover this m distance because the distance between one and 4 a.m. So this is the stern travel. Even so know of this Stephen travels in distance to reach for and this distances some multiple off this loop minus key. So for if we look at me too, if it takes some multiple of this or loop, then it will reach here again. If we subtract k distance, If we decrease their distance by care units, their distance will be here. Or there is another way of looking at it. Ah, school. We can see that. CNN There's some C minus one times in. Listen, I just subjected medicine and person May Nesky. So this is another question. Seoul lets us even him. Plus in minus K. What is in minus Kate this company Distance off the Lucas in and minus key. So this is K, and this is in the minus. K did. This part is in minus care. Let's call it be. So this is see, in close, Andy. So in distance is equivalent to some multiple of this loop plus this distance be so if the if the second point is yet to and it also covers distance him because even has covered distance him so on. Both are moving in the same speed. So we do will also cover distance in. And this M is equivalent to taking some wrongs about this Luke notice cm last deep. This is the distantly, so it will also reach for so they're easily florid. Seldom looks so First, we need to find the point where the slow and five point is. Meat was the meat. We initialize one of the pointers to head and nobody advance booties for interest with the same speed off one stupor time and then little muted Miss starting north 16. Remove Loop From Linked List: in this video, we're going to see how removed from the link list. So we have been talking about identifying Look in the link list. Been finding or the switched element Oh, off the list that belongs to the loop. So we're used for its algorithm. For those on today, we will again use sure its algorithm will remove the loop. So remember, if you have not won, you're liberal. Use our request you to go or like to use really and see how to find the first element of the link list. Like in this case, trees the first element in off the linked list, which is part of the loop because you start traversing from the head of the list. So in this review ah, I will just do minor tweak in the court and nothing more. So the main content us the main concept that we will use. Oh, yeah. Oh, start in my previous really, where people were finding those first element of the loop. So, uh, earlier what we did, you know, very little dude, like we start from her than keep it slow and fast pointer and they meet somewhere. Let's say they meet at faith. Then we keep 1.85 on one point ahead. So far it is a place where day both slow and fast Point estimate where we confirmed that. Very look No Defend the settlement. We kept one pointed head and one pointed the place where the Met and then advised board. This point is very one step and they will Meter Street. So no, the question is how to remove their So the number in Oh, previously we were we were finding the first element of the North. We were comparing like, uh we were making you and he called to be rendered next. Similarly, Beato and we were also comparing there we were looking through this tin even is not equal to be to So when would even be to comes in this place, then it will be cool and then we've just bring it on. No point that was over four or know that belonged to the look. So in this real, instead of comparing this, we will compare We will look this still be wonder Next is not equal to be too rough Next. So in that case, we're will the Leuchter net or Leleu permitted when Buddha Pointers came to the street. No, when we use here or Sorry, even is there because in this case we're even. So let's said I started from here and we toured there, So even comes to seven. So any Celia will take that be ones. Next it's seven and because next is to or to the start from here. So it's next digit and it's next to for the journal articles. You know, between move here and even will move. No, I will take its next is three and its next He also three. So even the stuff here So we're we will turn it when even is theirs. And twist to that is one distance, one unit distance of everyone the first Nord. Now we know that even Waas the pointer that Waas going through the loop So it's next to the first nor so we know that no even is pointing to little last Nord. So after this Leuchter Minutes So we will not use this, you know use this condition Still be wonder Next is not equal to p two wrote next And once this looked or minutes then we will make you go under next to Courtnall, and we're done. We have removed the look because even is no, don't last element. So what will be the major? We will get rid off. So it's next toe pointing to three. The first element of the look. No, it will point to No, for this link will order. Just so when we know, Start reversing. From there we will go. 1234567 Yet. And no, it's next. Didn't also it will tell me so this new list becomes 12 So we removed the cycle from the list so quickly. Oh, I will give him. So this would ever court that we use for finding the first element off the No. So we can just mortifying the score just to learn more to figures in his new dude. So we will name it. Removal and Noah, we were taking this low is not equal to first. So instead of really tick So this is the earlier part where we were just finding the first woman we're finding the No, this is the case here. We're actually finding the first element so little, right? Okay. So, no. When this look permits. The pointers are one unit. Distance from the first north, Off the look so slow. What haired so fast with the part off the loop. So what we will do? We will make first mixed the court a little point for conform or poor point. Oh, in the last video yard inserted loop and then entered the beginning of the list. So let's sit on. I have not yet removed the look so you can see that this was the list. One toe 21 2 53 we're moving people. This next wonder off 3 to 20 to create the look. Using this create Lou function. And if after creating the look, we tried toe bring the list, it will not terminate so they can give it quick. Never. So you can see that 21 to 53 20 again off to you to again Start separating. So I couldn't do it. The first Children don't look No whatever, Lou, I will not bring this First I will remove the loop and then print a list. I am done. Nothing just removed the look and no see after creating the loop with when did 20 where the first element of the look. No, I removed the look on now entered the list on remove a little and we get back doors. No listeners, we heard. So this is how we will We can modify the first algorithm for finding out the first elements for special one application off large algorithm. There we, Sigurd. Or is there if you look in the list or north in the second a politician refund or what do you do? First element off the loop. And no, we have used the same algorithm to remove the look. 17. Check if Linked List is Palindrome: in this video. We're going to see how the check the Nords off the link list. Former palindrome. So first we need to know what is appellant room. So I have given three temples here that first tour palindromes, and the 3rd 1 is north. So here you can see the partner first. Little it a on the last letter j similarly second last TB Secondly, also be. Then we have C and see, and then be so did you complete symmetry for you, Roy? Line from the middle element. Then the left transitive look like a mirror image sees nearest to dis middens there also. So first in lost their same second and second last earth seemed third, Inter Lester's him. And so until it reaches the middle element. So this was the case where we heard one middle element and we heard or number off letters? No, Let's see when we have even more litters like here. We have six letters here. We had seven letter. So there there is normally little mint. What did your plane, which will be worried business string. So here again, you can see these are usually made it off each other, so sees here sees here, then be And you're also be in the 1st 20 a in the last 20 years. So these tour palindrome whereas in the case off third, this is the middle lane, the street You will find it season, article two D or if you start wrong, this age forest is equal to lost, so that's good. Second is equal to second last are suitable. The third is not equal to third list, so this violates net property. So this is not open in room. So I have taken two examples of linguists, one with or lint, one with even land. And both are well in rooms. Exactly. Ah, these airlink list and off to these two were grated link list out of that. So how can we sick that is the link list represents a pair in remote. You're just given the going to tell her. So there are a few mentors to do that. So first simplest in Italy. Let's take this example. This is a smaller room, So using stuck last in for store. So they learned that inserted lost is the one that will be removed first. So leg keep something on top off each other. We have one book. I kept another book on top of their than under book. So this terrible on the top. But when I did start removing one way one, This is the book nerd I will remove first. So lost in is the food store. So how can be sold this using stuck? So we will start traversing the list. So I will start from a and when made Trevor saving you. Start working deterministic Who? I have a stuck. So for still when did you so here Then we moved toe me. So in certain be I didn't see. Then again, see and then me And in June E so when we start whopping from this stack, the top 11 will so no, we are traverse the list list ones and created Desist Akkus No, we start traversing again. So again a. We will start from the first note that will be do for smallholder link list. But they all went on the top of the stack will be the last north of the link list because the elements are inserted in the reverse order. So effectively, this is the last element. This is the second last element Third lost. And this is the first element. So no in palindrome people comparing first with last second with second last. So here also so again we start traversing the You're here for Stillman TV. Andi, open this element. So if actually this is the last element. So we see that this is in this a what are seem so first in last element, it seem no move to next element Be Now this element has been popped out. So bees on the top. So again we will quote in the top element and it's b which is similar this Then we will move here at sea and again the FC. Then again, see, and then finally, second lasted be in here, Olson. Then we will move to last Element A. There is only one element left in the stock, and that is a So you see there, uh oh satisfies the property for Palin room. So we will say that your spelling room, But in this case, or did the time complexity which year was the least voice letters ordered in So time is ordered him on space space, older disorder, and because you're keeping a stuck offstage. And where is the number of elements in the list? So this is a good solution. But here we have time. Complexity is obviously cannot be less than order. And because we have to travel to the list a terrible year also using a dismal order in space. So we will try some other approach. So in this separate, what I will do, I will find them in the ligament. Fine, middle element. Then reverse the second off off list, then chick there for stern securing offs or seem Then finally reverse this secure enough again to get rid the list originalist because you don't want protein the list So what I'm trying to do here like we have to compare this first week Last Bartoli, Lueder. So what? We'll do first find the middle element. So here we have or even number of elements. So this will point to the middle. Both of these can liminal but that I had explained in my earlier lectures so we can find the middle element. So in that case, we were taking this 2nd 1 at the middle. So this will be our middle element. True, this part is also linked list in itself. Because this is the forced Nord we can treat. Decided on go next. Next. So even finding the little mints who were Bender sees the middle element, then rewards the second off. So what we will get So we will get a year Me is and C year after reversing this second off . No, we keep toe winders one here and I don't do here in the second off after your single list and I will advance mood these point this way once too. So both these are currently so be very cool. Remember, this is the last Children because we have reversed. So it comes here. This is the second last and this is the third list. And here beer for 2nd 3rd So here in years him who I will add wants to this and no VfB. And this will move here. So this is also be so when we find in equality evil stop and say that it's not building room here getting equality so we'll keep going. So again, see? So all ours him And now we have travels this list and also this list to use hitter. Yes. This is a palindrome. And once we're done, we were looking at your post this second off and get back towards me. So in this case, were to the time complexity. Yeah, travels the list of so again time, complexity. Evil will be ordering, but space complexity. We're just keeping a few pointers. Like the middle Lord. We're storing the middle orb. So that will be the pointer well used. Well traversing toe. Second of all the list and one winter for travelers in the first off the list. So just two pointers. So constant number of pointers. And this will not depend on the number of elements in the list. So space complexity, order one tangle, complexities order and buried in the case of using stack were both space and time complexity in order one order in. So this would be a better solution. No, I had no You made a complete really on signing the middle element earn also reversing the list. So both these concepts are used in the second metal so you can watch those. Really? If you want to know how to reverse a list I have given when I creative solution and one recursive forties and four rivers in the list 18. Swap Nodes of a Linked List without copy: in this, really? We're going to see how for the number off languished without copping them like eyes were given a link list. This is the first morning there. And let's save your ass there, set up the Nords and for or friends like. So when you even you think that we know travel the list from the next reform toe Me? No, it's reason. Or we know exactly where we want to stop who enslaved So we'll even there, so to wear and sleep. So we will see. When we started trading, we see that we there So what? Five years and continue further Still, I find other north that disfavor and put were so simply copping these values. But this is a very expensive process. In this case, it's very cheap process because you over link listening Lord had just one element that is one in teacher but one, nor can represent a very big Our district is also a very big big record like ah e commerce . I'd maintains the list off its our customers. Who in their port is we Tatum, for that can continue. The name of the customer is no towboat. The list off items here, politician in the past and on ward dudes on so on many other fields like telephone number address. It's a trick. So this can be, ah, very big, uh, structured in itself. And if we start copping one way one, then it will be cost your presence over a me that we should be able to do this for presenting one time. It is costing time and it's a Lord. You turn on the sides of the editor so we have next pointers so over aims would be to just some change of pointers. So that will take Constantine, whom, if we have to serve any to Lourdes in a link list. So we have one or two years. Let's in order a and somewhere in the list via Norby. So the result should be dirt. Be sure to come here a sort This Nord internal should come here and you deserve one previous known that this went into this new order and Bill, is it next mood similarly, for me, for let's say we have this previous Morden entryway be and next Nordea will be notably and a and similarly for would be gave me Andrabi so We have two pointers here and two pointers here. So in there and what should happen. So be useful this pointer instead of pointing toe a So let me first brought the complete picture. So you see that you earlier pointing to a no peace pointing Toby. So basically, we need to changed this Quinter and make it a point to May Then be was pointing to and be or tell be spending too in a in the resulting. So this point, this would also be of Richard two point here. No look at decide. Bebe was pointing to be no individual. Peavy's sore point to a so this pointers would be a rigid two point here. So this is third of reason. And now it was pointing to in a what? No individual is going toe nb full this this point just would we have Richard? The point is this nb so four poor interesting you there needed on all these two become equal the story Kurland So changing this for inter takes cost in time. So this would be over approach. No, dear. A few scenarios here, like here we heard a notional but you just normal. Who's next we're updating, but it may be possible that we are asked to step two notes. Audiovisual needed head? No. Then there is no previous no previous No. Reasonable. So we can handle that case separately. So in that case, what will happen? This force would come here and once would come here. And the head Norbu. So here Normal was cleared, pointing to one. No, I had a normal point to food. So first of all, one will once next going to flee. Go in the desert. When will come here and three will going toe one and porcelain point. So this is the first time here. One we're going to flare. And four bill 40.22 So whatever was the next one. Poor Bill when Children next to for their and whatever was the next to four when we're going to there. So boots next for interest are exchanged Course next becomes too for whatever was the next of one becomes next up. Second element. So we have a Richard this No, the previously remains him So it's previous force previous or no point one on once previous appoint toe for but one has no previous so instead over there we've been changed. Heard and heritable point here. No, If you re draw this picture, what will happen here? It is wanting to four. So let's draw food and four is no pointing toe from droids. Next, keep during the next off. Other who is winding toe three threes, no pointing toe. One. Everyone is no pointing to fleet and flavours finding to six on sex to Mel food. There's the miners thing required when one of the North Sea's heard similarly one. Ah, may I think there no other case. So in the simple case of there, none of the North's is heard. We just ended devious and next pointers. So the next of this should point to the next off other Nord and vice versa. And the previous off one Nord should point to No, they're normal. Who four point or exchanges here Also, Food Wonder continues. No, uh, let's write this in the court. So are no. We'll start writing a function for sweeping the nodes, and it's true. Take one pointer to point to that, because he had no can also be abated on two integers, which will denote the values store. There the Nords full. Let's are the fuel this cases like. If both value your same, then return or if the point there is none in the undertone or the head. Nordea's no that is listed empty than also return Then for traversing the list we will need couldn't point only one previous point to So this will be the current normal where we are in the list on it in This will be previous. No. So these two bill in government do next. Next. Well, we will be traversed into the list and whenever we find that the value at the current nor did he could do A or B. Then we we will save their for infertile lordy and normal B and also deal previous to this previous to this previous him. Please be so No, let's traversed salute. So we are interested in one Onley two cases one if the North is you or nordeste me for these toward the cases were interested in In this case, we will save, nor they call to current review sees acquittal previous until early in this case, more musical toe current and previous musical too clears and then we will what did the previous and current pointers for whatever was current. No becomes previous on current becomes its next. Then when this loop terminates, then we will reach to the end. Because then only current will we know Andi. It may be possible looting there'd be did not find either a or B or boat in that case, these New York's criminal, because we did not find any and it's terminal or we did not find be determined. So once this more or this looked or Mitch, we will check that if North seasonal or Bismol then return because we did not find about the value, so we don't have to. Lourdes, we need to nails to from them. If the two notes are not present, we cannot full here. We're guaranteed that when varies toe this point both more than Norby will represent because if any one of them are missing, then we'll return. But refusing on guaranteed we go to be so in one example that if heard nor was one of the notes than its previous did not exist. So their dismissal case. So if previous age person we will earned alert case, it means there no Izard Similarly, we need to add Discuss in that case, be there. No. What should we do here? You previews his prison What we were doing. So whatever was the previous mold. So what they were with the previous off A It's next word earlier pointing to a but no, it's next going to be. And similarly for the previous off me. So we were right. Exactly that leave years off is next. So are leery Rose. So this is the existing stew. So we will attend it when Toby similarly poor Toby previous off me was pointing to more be so This was the existing state. We will change it. Make it a point to a So we're done with this case? No. What should we do it then? North Asia Suban Nord Izzard supported decision you and this isn't be for Asia than women mix beers The new heard So I heard some point Toby. And if Besart then make it went to a so in the else case we will write exactly there. So if North aged the no heard points to Moby And if Norman Beazer then heard points to mold a So we have changed the previous pointers. No, we need to upgrade the next pointers. Who is next? So even no point to next Toby. And we even know going to next to stay. So we will change that. So we need a temporary point to for that. And still one of the next winter's here. No, we will up, dude. More is next to point to no more So whatever was nor bees next becomes, nor is next. And whatever was there earlier more is next. So no, it submitted. So we had saved the state. What was the next off Nordion to them? So whatever was the next tough. Nor did know becomes the next tough Norby and we're done will be ever Richard. The next pointers on the previous pointers a No let's sickness bullets for Sprint work is the list. So we have this list looks for 20 and 50. So for nodes 2050 London during the list. Okay, so he earlier 20 Wazir people years. So in place off 20 becomes And in the place of 50 twenties there No, let's stick another case where we are slapping her doll for food. Let's take 10 and 50. So what should be here, Pip. Peace would come out there'd and 10 sorta go here. Who looks Brender. Okay, So earlier 10 was heard and 50 was there. No. 50 has come here. It's weird and then comes here. So, uh, let's stick to wear distant dogs, Fool. Let's take 10 and 20. So we see that 20 and 10. It was 10 and 20 and it becomes 20 and 10. Another part of the list moments in So I think it takes care of for Lucas is so in this way , Lewis saw how disrupt to norms of the linked list without copping because copies very costly a prison when the North contents very complex objects. So we this whole prison is constant time of prison. We go there, we do just for point updates. 19. Doubly Linked List - Introduction: in this video, you will see What is it? A blink list? And always you're different from a single link list. Water, its advantages and water. It's the servant is. So, if you know, singly link list, you know that it's represented by two feels in order. So first part, indeed, which contained the actual later and it's called a link list because it's a list off Lincoln words nor Third Lingam himself. Let's say there are three numbers their time story 10 20 perky, and these need not be contiguous. So these maybe at address 100 this may be it. A store that address fit in the memory. And this is, let's set address 500. So we have the values there, and when we have one extra our pointer, which is stools, the address off Next normal. So here, 50 restored because it's next. His store that address 50 single earlier 500 is stored, so in picture to really we can represent it with a narrow because it's just during the address off next, and whatever is the last norm. There is no next to it, so it's next dismal, and we just keep the store their dress. Oh, source node in some special variable called head who heard his a point which is storing 100 . So we have just this value and using this weekend travels the whole link list on Goran cooled we will represent it as it just struck two so strict, normal And then we have one data int on one north point, which is next. And then we were given just 1.2 heard heard in this case, this will be pointing to this normal and using this weekend rate here the next. So then we will get their dress off. They will get access to this node. Similarly, is they do next of this we will get access to this. No, let's see what digital link list. So the same three numbers 10 don't be. And 30 we're storing the same three numbers and let's say the same addresses 155 100. So here, instead, off next point of rear one previous and one next pointed. So this is the previous and this is still the same next pointer. So this will be storing 50 and there is one previous so this more will also have in fourth . What notice Coming before it. So it was 200 because it's previous noticed or that address 100 similarly next on this previous. So this is a story lavender on this previous is during this 50 and the next off last year, obviously on the previous off Street Ultimate. Because there's this is the first note and very no previous and again we're storing the point of two first Mobile. So in court there will be slight change so earlier. Weird Internet er it's still there. Then we're the North Point to next in the single link list. It's still there. What? We have added one extra field previous. This was more presenting north in singly link list. It's indolent list only now why do we need to use the real interest? Why not singly link list? So you see there pill. It's the A single link list Gen 20 and 30 same example. So in this case is we're currently let severe trading the link list or were given a pointed toe some more in the link list. That's a current and we have this. Nord has no influence or to its previous north. If we want toe find what is the previous? No. We will again start from there and store two pointers. Or keep comparing the next off the running point and see if it's equal to current. Then this is the previous North and we will return this. But in a doubly linked list, we have this previous. We have this next. So this year Caron cleared this criticism Been If we do current next, we will know 30 and if we do current previous, then we will know it's still so we're we can move in both directions. Jay Rosen, forward Derickson as Willis back or drugs This is not lorded singly linguist Water. The other at one business. So Foster wanted. Was that worsen in forward Rixon as villains? Backward direction. So this was when everyone then the next day at Wantage is there given an order we can find the previous as villas Next. So busy Samos Burley on the next ones do is they're supposedly want to insert a second reason than what we will need to do. We will come out the second point second pretty since point really pointing at Second World and we want to let censored after second. So here it's next will be the new norm and it's next will be biz Nord. But let's say one. I have given you a point that insert in new norm before current. The novel you insert before you have don't have access to its previous north. So again you will have to start from beginning. But very few are given some point that I have appointed current, which is pointing to some Norden a link list and you have to uncertain just before that. So what do you do? You will create in, you know, Andi So make its previous switchboard earlier pointing here, move this to this and you have previously street of it so make its next point to here and its previous here and it's next here. So you're done. You don't need to traverse the entire list. Similarly, when you're pulled that or delete this Nord the North pointed at a given point of current. So what you will do you know that current is pointing to 20 so you will find its previous and make its next 200.0 30 and you will go to its next and make its previous point to here and then delete Disney old but the same problem If you're given that I have a current pointer pointing to some Norden singly linguist, delete this Nord so you cannot simply delete it because it will break the list into two parts. You have to make the next off 10.2 30 also. So for that you will need to know the previous note also given a no, we will again start from the beginning and stop here. Stole the serious make its next going to 30 then delete and then you're done. So you see there descend An insertion given a pointer is very easy in orderly link list So in certainly listen is easier been next that one places that in single link list to reverse the list You have trouble quite ah lord of his work But in this case you don't need to reverse at all You just go to the last normal or you can also store it in a separate very well tell and just reversing backwards printed, then print its previous than previous on pillories There'd but you cannot do this in singling list you cannot into its previous because there is no previous. You're just allowed to move it forward, Reckson. So re worsen. North record. So this is another had wanted no water Are some deserve on business off the link list. So the only decide one is that you can see is there in the Lord we A data we have next and the previous There isn't singly link list were just these two fields. So you see that here there is one external pointer. So to store the same amount of data here we're three data 20 years. So we each nor was taking a space off an indigent and one point. But in this case, in the second case, the same information to store the same information we need when ent and two pointers. So it's sticking one extra pointer Arnold, but oh, so this is the main disappointed, but in practical applications that will not look much afraid is decided wanted because here you had just four by itself. Data on before that you were storing two extra point is also so it's comparable with respect to later or in practical situations. Ubilla store much more complicated data structures in the north and that will not be just four words that maybe oh many, many fields inside their destructive, so adding just one extra point will not look seem to be big over it, so that so ah represent link list doubly linked list in memory in the next reel, youth, or we will see how to insert early kinda lead return other presents in the link list. 20. Odd Even Linked List: two reveals all a linked list based problem. And here the task is to group together all the even an ordinary. And by ordinary, we mean the position of the North, not the value in the north. It may be possible that all values a road. Then we was called at this first North Cardinal 50 Lord. These are our notes and second for six tents on these North, sir. Even notes, irrespective of what value there holding, whether they're whirling order or even and the task here is to do it in order. In time. That is linear time, and you don't have to use any extra space. So time complexities would be order him. Where n is the number of nodes in a link list and the space conflicts. This would be ordered. Who won. So let's see. It's not a problem. If you know if you can reverse a link list, then ah, you will most likely solve discussion as well. So let's understand it first. So this is or in a link list, and after grouping them, this 13 and five comes first followed way on leaving notes, and don't be confused or dis values these can be anything. Order, even your position matters. So this is the 1st 47 3rd reason in this case for Houston in value are same. So how should we approach this? So let's see. You see that this is the next pointer off this first Lord. So just quickly Remainder recap off Link Lisnard. So in order has your value in this case into your value earned in next point. And this next pointer is itself a pointer to another lord on decisions. So the other two values that are denoted by one linked list Nord So here we will store the value and then the second sex and well written next which will store their dress off next. Norden the list. So this aero denotes the next point. So what we have to do? We have to make this next going to and this next can hold only one value. So if we make its next point toe this Nord then this connection will be gone. Similarly, we have to make this next point to this and again this next point to this and this next point. Do this. So this is the thing we have to do for Still there is the end And so it looks very intuitive. What you have to do here. If you do this, then your task is done. Ah, you will just need to do one more thing. So here. Ah, After Let Sylvia made these changes. So how we can do it? We will keep one or did snore pointer And one even more pointers initially pointing to first and second notes. So what we can do? We can make ord next. That didn't make this aero. Where should I point this arrow even next? So where do it is the next off even on what is the next off even next of you and is currently tree we have not yet seen these arrows were looking into the or is no list. So next off even his three so make or next or this one so once next will now become three. So it will be 13 And we have not changed any other point after this A statement So this area is introduced and this area is gone? No, While the saloon seeing our award a point of order Quito! Order next! So our next is three These oil lord initially and it's next were murdered three. No, we moved ward here. So no authorities here. And this connection is dumb even is there So what we can do? Ah, we will make the same logic because you were repeating the logic. It's next we're making events. Next. Whatever. What events? Next We're making this next and similarly evens Next we're making whatever is the next towards next. So they have already moved or one step aired tilting their before playing. This logic when we're playing this logic toward its next element is the current even. And when we will have played this same logic to even we already moved next. Oh, are as its next Nord. So what's next is or is this one? Currently we have sifted here So it's next is four So now even next is four. So this area is introduced and this area you gone since this a broken just to store one address. So this will be going implicitly And now our task is to move even here. So what we will do even in Quito even next. So now you understand the logic. After this one step, we will take this in peer and consider it as one step once next has become three. Or it is here another point recipient nor change for threes. Next will still before and force mixed his played. And And what we have done here do do is there who's next is four and force next is five and six and even is here so even is here or it is here So this is the ah state off this links link list After one step, we have picking ones too. So we have You can see two lists diverging ah to list converting into one. So what we can do next make uh so even is pointing here or this pointy here So is the next point you tear and this area here then we will have done so Finally we will be left to it. 13 slave none. And 24 No. So we will have these to link list now completely separated from each other. Then our task will be that whatever is the current ord make its next point to this. So then they will get this 1135 24 So for that we will keep two additional variables. We will keep this airs head or we'll call it ordered and the next we will call it even heard. Heard even we can any solicit in the beginning itself. And this will not change these orders even are. The point is well, which really changing. And in every step you're doing just distinct this four things. So make this area a point here, make this arrowpoint here and move this pointer so the next toward and move this current even though the next even so, we are done until this is step and we will repeat the same thing. This will keep repeating till we reach and and one of these become ill or strictly even becomes null. So let's Children through this example. So there are two kisses. Let's run through boot. This is the order case. We have ordered more if elements so after first step, it's orders here it's even. He's here. So we make this point here and no orgies here. And we make this point here and even is here in next step. What we will do, we will make this point here. An order comes here and we will make this Arab point here and even concerned. No, let's see, even as we come now. So we have one. It's next is three. So let's and George three. It's next. Is Fight Solarte Sandro Fight. It's next is no. We have not changed. And here the order will be here. We're nor changing her Lord. And here it even. No, there is no other connection in this list. Know what is the other one? No lords next, is it even we are detested. So it's independent. Who is here? And this is it. You can Who's next year's four force? Next? Dismal. So this is the state and orders. Here we go. After stinging it, we move toward next. So what we have to do? We have to do ord next, equal to its even. And it's even is in the beginning, all responding to the second element. So this next will point here and not know. So the final result will be 13 sleeve to four. No, and it's already is pointing here. So this is the new link list and their dearly English. You see that or Nords have come together for roadway even notes and we have to return the new new head off the new list. So we will return. Return it order. So this was the our case where even has become so next Look at the or even kiss. These are the only two possibilities. Either will it will have it. Oh, our number of notes or even normal notes. So it's already here. It's even is here, or these ear even is here. So we make this point here and no order comes here. And we make this point here and even comes here and again. We make this going to hear. But we will not do this when we see that. Ah, it's evens. Next dismal. Then we will not do this. So we will stop here. So once we stop here, what will relate to one It's next is three. It's next is four and it's an external. And, uh where is even even is here so we can write go food or better. It's confusing here, So this is even even his pointing here or is still pointing years since we did not change this next because you then ordered become ill and we were doing or did next is it's even this we have to do. And if our dismal then we will not be able to access is its next. So this These are the two things are you see, if we have our number of north, then even will become one in the still, so we don't need to worry about that. But if we have even know morphing lords, we will see that in this. In this last step, we will not do this so we will stop here itself and whatever is the even notes, it will both converse to the last note. So what we have to do of the up to do ord or next should be too 13 to 4. It's the results will be. Want to Sorry 13 to 4? No. So we were toward next. Equally to this is your Stephen decision toward It's even so we have seen you tear and return. So let's right the court for this. You can run through this example again, and it's very, very clear. It's I think it's much more rigid in reversing a link list, so let's write it in C plus. Let's first, then we will do it for Oh yeah, when Peyton. So if her dismal or here it is there. But it's next is null, that is, there is just one element one north. Then we don't need to do anything. Then simply return haired. Nothing required hills. We will create a few pointers. It's ord, it's even. That's it. And what will revalued? Because it is really good. And it's next Israeli we have already ticked earned. Or the call to it soared even according to achy, even know Well, even if even next then or next week or two even next. So this way we're making sure dirt or never becomes nil, so that in the end began a sane or next equal to ah, the head. Also, even it's if events next is none. Then we will look this case, Oh, events next seasonal here So we don't change this pointer but directly make its next point to it. Even so, exactly. That thing we're writing here and we're done so we will return. It's hard. So this steak is required for again reiterating this even number of norms even comes here. It's an external. So what we do, we make its next point to to notice the head off. Even so, it will be 13 So if evens next is null, that means there are no more or notes after that. So we're done with our notes. So we're ready to make the arts next point toe the first even which is too. And we will be done on the other ways. Or we could do if it did not enter this case and then or equal to or next even next, equal to or next and even in Quito even next and we're done. Finally, we need to return the hair, dolls, this sword, a sword. So then even becomes No, we will go in there and make this a step on also return. It's hard. So this will happen when the ah, our number of nodes way. Let's see. Oh, this is a case. So their order comes here at five. The life starting job. So order will and then always three pointing to the last or Donald after this loop ends and even will become ill in this case. So this is the this case even will become ill. But we have still not changed the R next to its even in this case. So we will do it in there and after the system flavours next will become to whatever Well, those for Stephen Lord. And in the even case, we stopped her prematurely. And when events next is numb so either even with a camel or events next will become one of these. This will become ill. In the case off our number of notes, this will become null in the case, off even number of jobs. So in this case, oh, we wouldn't make or next going to this. And in this case, Ah, we will do this after the loop. And so let's, isn't it. So it works for this case. Let's this one. So just I heard the case off even number of nodes, then want to then one and also empty. Let's try all these cases and it works for all of these expected Ansari Samer this one similar to submit and the soldiers and it accepted in sleeplessness. No, we will quickly cooperate and do the same thing for Java in Brighton. - And let's trey lie number 20 and this works as expected, so let's go ahead and submit So the soldiers and is accepted in your eyes will. No. We will write the same thing in Britain, my country. - And this works as expected, Solarte some and the solution is accepted in Brighton as well. 21. Delete a node in Linked List (No Head pointer): do, they will see how to delete in northern and link list. Andrea, trick your that You are not given Pointer toe the head of the list. If you're given a pointer to the head of the list and you're given in north or no pointer, what you can do is that you start from head start traversing the list, using this next point to and when you find that the given Nord matches with the current node, you keep track off one previous north also. So once you find reason that not to be deleted, you make this previous next point point to the next north. So this Nordic bypassed So no, When somebody travelers is this list, your C will start from here. It's next will come here and four on dulled So this two will never be printed and it will not be part of this list anymore. And you can absolutely free the memory occupied braiders. But there's this head is not given. You are just even pointed toe this so you don't have access to the previous naled, so you cannot make the next or previous point to the next off the north to be deleted. So let's see how we can achieve this. So here, let's say we want to delete this North three. This is done Noto ability. Let's call it in. So here what we have to do instead of deleting this nor this is our target, nor to delete it. So the list should become 1245 Threes are big on my past. So instead of deleting three here, we will delete next note. Since we have access to all the North after this current note, since we're given pointed to this known So what we will do, we will copy the contents off this next north to Disney World and then delete this not using the same trick that is make this next point to it's next. So let's see how we can do that. So, Lord, next equal to indoor next. So this is the next next and not, well equally toe next to nort. Well, so what will happen? This will not be holding four instead of three. So we are no 1 to 4 for flavor and no So this is the state after this lane. Next, what we will do next. We have to make this point of going toe the next off next equally toe next North. Next. So what will happen after this? It will be one. Do four and decision. This is next we have made in Norton next tickle to next North, next next door in next year's fire. So force next to becomes flavor and free. And this another four year olds appointing here. So this is next. And is it in? No, we can, you know, be able this if this is the head hair Dejan changed. So now if somebody travels is this list, what will you printed? Or we bring the list using or travels the list using next point. So one is the head. It's Next is to its next is four. It's next is fire. It's next is in the and this is the list. No, So this is bypassed and it's not used. And in sleeplessness, we can't even delete this so freedom memory. So this, nor did also diluted as well. So let's right the court for this in C plus plus Java and tighten. It's a very simple cordoned. The trick is here toe copy the contents of next North and delete the next note. And there are some conditions given that the link list always have two elements. At least all the North's values will be unique than Nord. The deleted, nor will not be still so. So you don't need to do the boundary. Six. You can it straight away, right? Your logic here and then We can't delete this next to freedom. Memory occupied with that. No alerts on it. So it's listening or not know. And this works. Let's summit and the soldiers And he accepted. No, we will do the same thing in Java, and the solution is accepted in Java as well. Finally, let's see Bite, uncle, and it's accepted in Brighton as well. So what is the time complexity Here? I'm complexities Order one. Since you just copy the contents off next North to the current Nord and then jeans the next pointer off current job and space complexities. Old order one. Since we're not using any space off daughter off the side of linguist were just using a temporal, and that is off one. So one in terms of time and space 22. Flatten a multi-level Doubly Linked List: in this problem, we have to flatten multilevel the brilliant list. So in a doubly link list we have in Next Pointer and a previous pointer here, we haven't additional pointer and that is child pointer. So you can see this is just one link list, one doubly link list and you will be given the reference off head Nord. So if you're giving appointed to the head node, you can travels the complete linguist. It's the next one is previous and this is child and it has three levels here. So after flattening, we have to make them like normal, doubly linked list. So all the tile pointless would be no and you should appear in a strict line. That is, they will have just previous and next pointers and no child pointers. So this entire hurting will come here after three. So three severe then all of her Children's would come here and then force would come similarly for this case, these two are the Children. This is the Children drink list, so it should come after it. So 78 the 11th will then 19 and then this complete things would be most here. So let's see one example, then it really more clear what is the requirement? So this is the input and this is a linked list. Nor the only difference is that in normal, doubly linked list, we're next in previous here we have child also and all three year themselves North pointers , Same type as this more details. And this is the input. So she'd riddled here till three it seem. Then after three, all its Children will come and then four is here for his here till tree it seem. And here also it's flattened so you can see a recursive. Oh, so listen, coming out here so it will call the flat and on its Children and these Children disturbed may itself be multilevel link list. It will again see that it has a child, so it will call Flattened on this. Now this is already flattened, so it will directly get inserted. So this will become seven. It then 11. Well, then this 19 will follow. So this is flirting toe this now the calling function. This will return to the calling from some this recursive function. So this return here and this entire thing after flattening will return here on the job off this more dessert. So this will be our current, and it will just insert this entire thing after itself. So it will keep a pointer off its next note or Lear next note and this recursive function will return. Uh, the deal Note also, what was the last note? So it returned the tailored and it knows what was it Still know it's seven. So it will make its next at seven previous off seven as this current node. And this is the tale. So the next off a less this next and previous off next test is still so, Doctor, wait, this entertaining will be in sorted here. So let's write a formal court for this. How we will do it. So we will have ah recursive function. Let's call it flatten Rick, and it will take it head point. So what it will do, uh, current will be equal to head on da Dale. We'll also be equal to head and we will continue till current is normal. Nautical to know. Then what we will do? Oh, we will check for child whether this current North has child or not. If it does not have any child Then move current to next. So if ah government has Jane So this is normal. Then what we will do. We will call this function on this. Recursive disregards the function on the child itself. So this is the child. So initially current is here. Let's also store next and we can also start til so all are here. There is no child, so make heretical to next. So current will come now here and next will come here. So next is always pointing to next off current. So next year currently here again music. If we test I'll or not know so again advance the current. So now current comes here. So currently Now here and next is here and nobody check if it has child or not. Yes, it has. So before advancing current to next note, our job is to flatten this child and inserted here. So if current Nortel is present, then Dale would equal to flatten Rick So we're calling this same function on its state. So this child is seven and this is the This is you the link list. Multilayered lovely link list in itself And this is the head for this for this new list list. So we will call flattened wreck on child. So you can a storyteller or you can pass current title. So this this will return the tail last north so that we can make its next point. This so ultimately this will re term Let's say it flattens it out and returns here So it returns 789 not 978 11 12 the 19 So it returns. This value and tail is pointing to this. Then what we will do, we will just need simple pointers changes So we're here current, So Oh, our current next. So this next is the green pointer and previous is the yellow pointer So current next or I should have returned it in green current Mexico toe till so what happens after this? This green is pointing to ah, current next to retailed due to mistake here. So now this green is pointing to this child. So we have Ah one, 23 And here this is pointing to seven. So this we have changed Then what we need to change or till next. So next often should be this four next So earlier next words for before we call this recursive Lee. So this list remains as it is. 78 11 12 9 10 And I am not drawing the arrows. But here we have both next and previous. And this is the deal. So till next becomes next. And next was for so four comes here four and after four, nothing will change So tense. Next is four. So let me draw in green. So this has changed with this line of court. Then what we will do. Couldn't Joe quarto? No. So this will be gone so earlier. What was happening? This when meeting this, you're to tell Lord is still pointing to the seven. We do not think this point No With setting it to know this will be gone. Otherwise it will be invalid list Know what remains Oh child Previous We have not said the previous of this seven. So it's previous would be this current or gain This is the current and this is for his next . So this also we will change So, uh, child previous equal to current and then we're done here. We have corrected these two pointers and also these are two pointers we have not added the previous off next as the till. So it may be a case that this was the three was the last note three of these. We're not existing in that case, next to terminal. So we will check if next is not know then next previous according to Dale. So what will happen? This wasn't next. Its previous is not set yet that Egypt's previous is still pointing to three. So this is the current state now and this is invalid in the region Invalid Ling heard of link list So this previous would be pointing to So we will make no change. But if next seasonal then we will not do it. We don't need to do it. This 10 will be the last So that's all and then we need to advance the current. So we have already flat in this part. So we can also add once current way one step. But it's better toe jump jump directly here since this is already flatter note So we will not need to travel this part again. So what we will do, we will do current according to tell here inside this and then if current is there then daily call to current since we have to return or they'll also from this function. So ultimately we will return till and we will make sure that we never reach it. So it will be do just still currently is well this tale will cheese current and current will be advanced When current becomes know this tale will stop here It will know that this is the last nor last last well valid note and we will return that. So let's right the court for this in C plus plus Java and fightem it should not be very tough. This is the same example I had just drawn it in simplified form. So we will need a recursive function which will return a tale. In this case, it's the function that sort returned the head So let's define a function. We can also achieve that by using a static till very well and then we will that will be served across different calls. Oh, let's call it Nord Start flirting Rick for recourses and noticed our head And here what we will do if it is there. It may be that this linguistic empty then we will not. We will simply return here if it is there. Then call flecked in Rick on this head and then return here. No, this is the mean logic North star current and still boat off head. And then, while current is not know, liquid couldn't change. And we also need to store the next so that when the flat in detail it does the deal, we will make the next off tail as the earlier next. So it's inserted between current and next. So if you see this diagram, this is the current tree and next is four. So whatever is the child know this link list? After flattening, this would be inserted in between current and next. So we need to store next, so there still will be returned and we will make the next off. This will be returned there still next off a less dissonant next. So we're storing next year. And if Charlie's there, then we will lose those Point Eric seniors and call it recursive Lee. So this child is the first Nordoff this next level off link list. So it's acting as a head for that on that will be flattened. Ultimately, if there is no telling what we will do. We will see here if there is no child, then couldn't equal to do next. Current will just keep incriminating to next. Next if there is no child, if there is child, then only we need to flatten it and ultimately next will become, since next is always one step ahead of current and this Louisville end. And finally we will return Dale from this, since this recursive function is returning the last note and let's right the other quarter . So tell his return to us. What we do tail next is next. It should be very in to do whatever we had seen in the logic 4.2 exchanges. So we will write it tails Next is next. Other thing is next previous would retail always we will doing piers, but there may be cases that next seasonal last note then, in that case, this should not read in the and couldn't next is for no pointing to the next, so it's you're not going to change. Onda had sort of been no, obviously, and sales let me write in together. So these two peers together tells next is next and next previously stale. So this happens in peer currents next to Terry and Child's. Previous is current and next we're making this a very listenable and no, we're advancing the current to tell since we saw her that since this is already flatten and we have inserted here, there is no point in moving current with just way one step and again taking those things. This party's already flat and for us, so simply jump current last still or you can even move to next, so current equal to tell. So this was just for your understanding that these things are occurring in peer. If next office be than previous Arby's, a. Similarly here. And if current is there, then tail will become. Current hotels are not become because we're sitting here next off tail and other things hotel to read the last value node until will always be there. Since we're moving to this function whenever there is a child, whenever we have a tail, then only beer capturing it otherwise tail tail will be pointing to the current only. So that's it. Let's see could. So this answer matches if you want to test more cases than you can write it like this. Let's say we want to see this case. A different scenario where this child is the last North notice. It's like one too. Then three for And this isn't that. Or maybe for result in order. Madrid style is there. So how we will define it. It should be one TUNEL than penal then for and again this works as expected. So let's submit. And this always any accepted and what will be the time complexity here. So we're starting from here and go to next. Go to next we found detailed. So we come here, go to next we found detail. We come here, go to next. This is basted here in between and we're not again coming to this. We're not double traversing these. We jumped the current total lost or tail and we continue the narrative Italy this returns and we advanced current from here to directly Tim. So we're not wasting North's multiple times. We're just wasting them ones from beginning to land. So if there are in Lourdes, it will be ordering time, time, complexity and we're not using any extra space only. Yes. Rickerson Stack will hold some values, but that is generally not counted in space complexity. But it's good that you understand that, or space will be occupied without recourse in a stack. So if you're doing it a creatively using a stack, then there you you use similar amount of space that can be a daughter off. And if all the north side like this like 234 there are no next next but only child child. Then ultimately, this will call this. This will call this so in the stack, all the north will be there so space can be ordered in time is also ordered. No, let's write the same thing in on Java. Not much changes required. And if you followed the explain its and in sleeplessness it should be should not be a big task here, and this solution works. So let's summit and it's accept written in Java. Finally, we will do it in Britain, and this also works as expected. Solarte submit and Peyton Solution is also accepted 23. Remove LinkedList Elements based on values: in this problem, we have to remove some of the north Promisingly link list based on the value of the North. So in this case, we removed all the notes which have a value off too. So this will be the result. So this is a very simple problem. But I will try to give a I treated as well as a recursive solution for this So that you, whenever asked, you can write both approaches. So first, let's look at the attractive. So in this case, let's say we want to delete for then what we will do. We will start from the beginning. This is the head North head is given to us and we have to return the new head. It may be possible that Delmon that we want to delete is in the beginning. In that case, head will be modified In other cases, head will remain the same in this case we have to delete for so we can keep ah, a few notes. We can have the basic narrative. Here is no return. If it is not know, then we keep two elements. One is current and this will trait from left right that is the only way of fight written missing Lee linguist. And for current, there is no previous more. So previous is here that is no So it's no So we imagine the current with the given value. If it's not same, our job is very simple. Just implement both of these. Soapy comes here, See, comes here, sees the current be the previous again. It's not equal to four. So again, advance vote of DEET. Now it matches. So when it matters, whatever task we have to make the next off previous going to next off current. So this link is broken and what we will do in simplicity want to three member. You can delete it also, but we will leave it as it is, and at once the current so current will always were wanting. So this is the state now one. It's next is to its next. His fight and rest of the link link list remains same previously is still here, since the next to be deleted so previous would be already one step before current. So there's this forest you can think of it. It's gone. So previous is still remain there. We will not move it. Just move the current again. It does not match over. Job is simple. Current becomes previous and current becomes its next. Now again, it matters. So move this link here. So what about what's next? And current comes here Previously means here only? No, when current isn't always stop. So let's write it again. We will return this head so we return here. So here it is. One it's next is to it's Next. Is this fight. There's only one next pointers. We'll be assigned it a new value. This will be gone next off his plate and next off flavors. So this is the new list, which is expected? No, let's take a look at another example Here is the head north that will be modified since trees were not. And we want to delete all the north with a value of three. So again, this is the current previously here? No. So it's equal to this so we cannot rate previous next equals do current next. This is what we're doing. Whenever current is equal to the given value, we make the next or previous point to the next off current and current moves here. What their previous inal. So this we can or Texas we cannot call next horn, another pointer or even in other languages we don't Next we're seasonal pointer is not valid. So we have to add any spell check for this that if current value it same as the given value then we check if previous is present then we do it. Otherwise we don't need to do it. Soapy remains here Current comes here and we also moved here to here for this A special case when previous is no we moved ahead since we know that previously just one step before the current. So in this case, current is the first note. That's why it's previous in model. It may be possible that we have a few three and we have diluted this this Now this is current. There is nothing before it So still previous is no so still head will be pointing here headed always pointing to the first note previous seasonal That simply means that current is currently first. No So just to make hair to the next of current Now this is gone Previous seasonal head is here Current is here It's not equal to three. So move it. Here he comes here becomes there again. Matters make this year and current comes here again Matches make previous Next of current against he comes here it does not match So he comes here he comes there No seasonals treatments No, let's write down this So here it is this too. So we started to It's next to this one fight. It's next season little So you see this is not expected Reeled So this is how we will do it attractively next How we will do it Recursive Lee So let's say we have putting argued one is the first note that we want to delete. So let's say this is the list and we want to delete before So here for is the first Nord And in other case let's it is in order scenario we have three to four. Oh too No, In both cases we want to delete for but in one case forage in the beginning. In other case, Ford is not in the beginning. So here it is. Here, here it is. Here. So how can we recursive liberated? We check of it captured into a listener. So since this function we have to return and new head. We will kept original very village equal to Let's call it delete note or let's call it f the main function that we have to write. And here we will pass Next, offered and the same value. Well, so what? This will do this Will We're passing this second nor to it so it will remove all the values from this No, this list and returned the new heard. And what we will do if heard well, is equal to Well, that means head will be deleted. In this case, we're Etem. It's so this is related So it's effectively this part else If it is not equal to this, we would sit head the next week or two. It's and then return home so it will work for both the cases here We're simply returning whatever this value returns. So it will delete four and returned this tree and we will return the street itself from the main function. And here this is the head. People again call the same function on this part. It will eat this and return to so we will set this it will return to and fight. This is a courtesy call. So what we will do? We will make threes next point to this and then return the street. So this is the list that will be returned. In this case. This recursive call will return 321 flight this gun and we're simply returning that this middle return. We can verify that it's correct. So let's write both the recursive. An iterative approach is so 1st 0 Villa writing sleeplessness. So let's at the base kiss if her dismal, then return head. Previous is no on currencies, I heard. So this is the main body where we rewrite the main logic. If it's not the case, then our life is very simple. Previous, he's advanced by ones who told the new current, lower current and you respect do both. More dysentery use current is couldn't next. No, let's right, though this case where the current value matches with this so there are a few scenarios. There may be possible that previous seasonal added we had seen in the explain ism. So if not previous, then I heard equal to current Next and current becomes got in the older ones to next here, irrespective of both these loops. But if previous is present, then what we will do previous next is equality couldn't next. This is what we're doing. You can also write it in one lane and finally we will return head and the solution is accepted and we're here. You can try a few times. It should improve. Since this is the best solution, it's often we're just making one part of this list and not more than that. No, let's write for the recursive this iterative court for all the three languages that do not take much time. Then we will come back to records it. So listen. - And the job is always in yours accepted. So it's right here. One millisecond No, we will write the same thing in title and the heightened solution it also accepted. Now we will write the recursive court. So what we will do make a copy of this on. We will comment on this iterative implement isn't on this basis remains the same If you're tempted, return otherwise what we will do it is not known. So we will recursive Lee call this function to remove all the North's having bell from SEC until last normal. So we're passing here next, instead of head on. The value remains seem so it will return something the head off the new list from visitors . They removed all those notes and then we have two scenarios. If heard well is equal to well, then in that case, head will be removed. So we are any very moving their head on the first note and we're looking from second till the last note and removing all the north better value well. And this is what exactly this has done in this case began. Simply return. It's but it is not. The case that is head will be unmodified, so it's next will be This had returned by this remove elements called and finally we will return and head for this case Onley for the second guess it will come here this call for the first case when her difficult do well it will return from here itself. So let's run it. You see, it's even sort of them attractive. So listen and this is accepted. And if you compare the time, you could to see similar numbers in some millisecond range, and it's also often so. It's just 34 lengths. You can write the same thing in Java and Python also 24. Reverse nodes in K-groups (Hard): in this problem, we have to reverse a link list, but not like normal English. Here we will be grouping notes, so we will be given one input k So we have toe take this group reverse the this part of the list. So every group just more link list in itself. This is the head off this link list. This is more link list. In this case, I'm talking or cake or two to it can be treated can before it can be as big as the number of the linguist itself. So you reverse A and B So let's head injury and be so in the result it should be be followed by you then here we have cnd so it should be de followed by C So you can see that we're reversing in a group off site K. So this we have to do. And if the side of linguist is, let's say in this case, six. This game may not be our director of this or a factor of this or in other words, in may not be perfect multiple off key. In that case, the last part we will have some number off link list which will be less than K. So what we have to do? We don't have to reverse them. We have to leave them as it is. For example, if you have seven and we have to divorce in groups of three, then we will reverse the 1st 3 than next tree and there will be one remaining or even there are eight. Then we will leave both both of the notes as it is so we will only reversed ill. So this in is see Time's Cape plus B. So this days left them K. So this part will not be reversed. Every other see part will be reversed. Ing groups off. Okay, so let's see how to solve it. In fact, this is one of the problems where we don't have to solve anything. Whatever is given in the question noted itself, the solution that is the solution Is that rivers? The first part. It was the next key part, and this time will be the last in this since this was earlier first. So make the next off this point to the first off, reverse this part and and so on, so there's nothing to solve it But it's still a elite core heart problems, since there are so many pointer updates that you need to make that there is a high chance of making mistakes. There's nothing to gear on. Lee. Thing is the trick in writing the court. So that's where it's least good hard. So let's see. Let's take any jumping. That's it. We're solving fork equal to two. Analysts say we have a link list of state seven and next off, this is nothing. So how we will solve it. So the results will be clearly to one. These two rivers then do one, followed by four treatment and 65 and seven. So what we will do here now? First, we will take the current off the list so we will do a scan of this list and let's story num num will turn out to be seven. Since in the beginning, we don't know how many elements are there in the list were just given the point off first moved with record head This were given were also given K. These two are the inputs, so first to be, scan it and count the number of nodes and then what we will do. We will have some pointers just like our normal reverse linguist case. So, in a normal reversing of link list, we keep track off current. We keep track off next we keep track off previous and what we do next off current is made previous. So this is the next pointer and this is the previous Let's see, this is current. This is next. Next off, this is previous. So be make this point to this similar living current comes here, we make its next 0.2 previous so feels like everything. So current comes here. Previous comes here, Next comes here and we're just going and changing these pointers. Another intimately seven is pointing to six sixes, pointing to fight and so on. So this was Norman. Reverse the general case here. We have to do in groups off key. So again we will have some point too smart. There will be some differences. We will have some more pointers than normal reversal. So we will have one previous pointer and previously initial eternal previous is pointing here. This is current got in disappointing you and next will be pointing here. And let's say we have at least two elements we will return when we have less than two elements that will be one of our base. Case is so this is initial initially it is. And previously here current easier next easier, as the name says. And if gays one, then we have to reverse in groups off one. So this one node itself if you reverse it, nothing changes here. Also, nothing changes. So if gauged once you return the initial list only it's OK. We're talking work equal to two or more. So this is doing is the reason what else? After Iverson, the head will change. So whatever is the kid element getting old that will become the head and that's very obvious. You will reverse this part so it will become two, followed by a one the first group off K. Next we will regard these trees. It will be four followed by three and the other part of the list. So you can see that too is in the beginning. So who wielded a new herd? So we will have a new pointer according new hurt. Let me right here. New word And this will restrict always Kate Element. So you can, either while a scanning the list to get the current there itself. Then current becomes key. Or take the point of that note and assign it to new heard. Or you can keep it now for no, we can even assigned during reversal the boat, our thing. So we have four pointers. No new hurt Previous current Next bottle's we will have one. They'll also. So when we're starting, when we're in the beginning off, it gets Sigmund. So we're always reversing in groups off K. So this is some general. He notes that here another keynoter here and so on. So this is the list. So whatever is the beginning off this first Nord after reversal? So whatever is in the beginning, Once we reverse this part, this will come here in there and and this will hold true for everything. All the casing mints. So there's maybe you're keeping track off. We're storing this first more in some variable. We will call it till since after reversal, this not will become ill. So that's what we're calling it till and then this pointed remains entities. And then we start in new set off reversal. So this logic will be very similar to reversing a link list this inner part. And then we moved to the next segment, each segment as kennels. So when we're here, this is the new till. So this part is reversed so you can think off. We're done with this and we're having this part followed by this part, since this part is reversed and now we will devote this part. So this is our tail with a story and whatever was the previous tale that is this. So let's call it till one. And this is tell toe. So this is still one. So we're storing two tails since we have to join this. So tell one next four point in this current. So then we will have its next point here and this is your first. So you can think off. This link has gone so that way. We're keeping track of this. Once we have reversed this this tale to will come here and what should we do know whatever is the last note. So we're advancing current, so current will come here and this will be previous. So we're storing this tale because it's next to we will make Disney World. So this has now come here so make still one next equal to previous. So when we're reversing a linked list what we're doing we're keeping these three values current next and previous. So when we have reversed too this part and we advance current here. So current comes here. So in sort of what I'm trying to tell her is that we're keeping track off two pills. One is this part of the previous segment that we just reversed and this is currently which we're working on. So before starting, we know that the first element the first note is going to become the tail That's wavy assigning tell to And this tale one is the last note or the actual tale of the previous linguist previous a smaller linguist offside key. So when we're done with this reversal, what will happen Current will move to the next segment. Previous will come to this part. So this is previous So why we're storing this is that until we reverse this part this previous, we will not have a pointer to this The last note It will only be available when we reverse this part. So once this is reversed. We know know that we have putting this this point this note So that's why what we will do till next is previous. And after that we will move to the next segment. So this still too is doing the job off till one. So we will update tailbone equal to tell you and whatever is the first element here. In the next segment this will become the last element. So tell you will be objected to current. So this is the current. This is next. This was previous so previous Begin reset TUNEL every time and automatically after one sift previous will come here and so on. So you get the idea Let's so right 1/4 a small court Then we will run through it. So let's right we have ah previous previous libidinal previously here and I'm not bordered . What new heard knew it We can either update in the beginning while counting the notes It will always be there to know And let's say we're working with K quarto. So this is the first part previously here Current is here. Let's call it just see and next to in and tell when there was no previous segment. So tell one is the tail off previous segment previous list offsides, kid. But for the first segment, there's no previous think. So you can think off till one pointing here, Colonel. This is no until you will be distinct. The first note since we know that this will become the end of this. So this is Tito and know what we will do? Let's ride the normal court of reversal. So next next to this end, or let's register in and equal toe couldn't next, which is already there in the beginning and couldn't next equal to previous. This is what we do and then previous is updated to current. And currently that Richard next. So we know that our lists I just kids. So we will repeat it, Kate Times. So this will be repeater your times for one block again. We will move to next block and this will again be repeated a few times. And when we will repeat so easily any seven. So first time we reverse this part. Repeat this Look for Kate times we have to revert just this part. So five elements that left so after this what we do we doing there in minus equal. Okay, so this is part of some bigger loop. This is a smaller look which runs care times. And after reversing what we do still one next. Its previous exactly what we had written here and after conduct Still one up close to tell to till toe becomes current. That is the first Nordoff next segment and previous Very sick, you know. So let's run through this example currently here next year everything is fine. Everything is in place and we repeated k times notice two times. So the next equal to current next to next comes here and current next. His previous current next is previous. So this is the next off current. So it's next, his previous but previous seasonal. So this link is gone. Next What? We left him previous becomes current. So this previous comes here. So no previous it here and current comes here to the next. So now current is here. So this happens after we have done it. One thing it will read it again. Second time again, next equal to current. Next. So what is current? This it's next to three. Next comes here so now in his ear. So these are the latest updates and current next his previous. So this arrow Well, no 0.2 previous previous is one. So let me redo it. So this is no pointing to one and previous equal to current So previous no comes here and current comes here. We have done it two times. So this will end here and no become here and here. We need a check If till one is present or not, since in the beginning Tale one will be No, there is nothing to the previous on this. This is the first block. So if tale is there, it's next 1.2 previous which is this? So you see, at the end of this reversal on this block, previous is pointing to the last note or this has become the first note in this block. Heard of this book and current is pointing to the beginning off next block. So since tail is nearly here, we will not execute this and no tail becomes till two. So tell one becomes still that is one. So tell one is pointing to one. So this is Stephen. Empty two becomes current. Since we know that we have not yet started the reversal. And after the reversal, tree will become the deal. So guilt comes here. So tell me who is here and previous really signal. So previous is again and read equipment in Bikey since we have reversed ailments, so no. And he's five? No. So it was seven. It dick lamented to fight? No, this Louisville execute again until que becomes less them until then, becomes less than K. So if we have less than key elements left, we will not reverse anything. So this order Luke Wilson until and is greater than he called. Okay, so five is more than two. So this Louisville again drum No, let's do it again. Next equal to current Next. Next comes here current next His previous previous is no. So this link effectively goes of it previous his current so previous comes here Current comes here So this is after one time It will be done to times So again next comes here current next his previous so force next phase three reviews His current previous comes here . Current comes here and this block ends here. So at the end of his block I'm reiterating previous is pointing to the head on that block. Current is pointing to the head off. Next look and what we will do. This timetable is present till next his previous. So that's why we were storing this still. So let me read. Right. So who is the 1st 1 here? So too. And it's next is one and Dale is pointing here even And now we have food for next is three and tell you is here I returned the same thing and then we have 567 know what we're doing? Tale one next next of one is previous and previous is at four. So this is previous So this linkage added here then till one comes here, end off this block and he too is here The beginning off next block on previous again, Very set toe empty and again detriment in So now in his and minus two artistry. So this is the state. So you can see that this party than 21 for three. Now again, we will do something here. So what will happen? This will be gone. The six will point toe five and the current will come here previous will come here. So again, our Steven's next. That is next off 3.2 previous 96. And again, till one will come here and at the place of t two and tell you will come here. So let me read. Write to one. This is four. This is three. It's next to six. Its next display and then we have seven. Uh, so we will do it. Is nothing here? Deal to next is equal to current. This also we will do here so that we're adding it this link before starting the reversal Onley after reversal, we will change it to appropriate value so you can see that this link is now reversed. This party reversed this party host this party reversed and this is left as duties. So now let's implement this logic in court. We will like didn't different languages. So if there is no or heard in external ready there, just one element or cayes one, then the list is not changed. Otherwise we keep the count any do and you know the count or number of north and we will I trade through this list. So until really is the end of the list. What we do in placeless and current equal to couldn't next. So then this Liukin's this and will hold account. So this is very tribute. Nothing to bother here to the main logically start now. So some pointers previous it will be no. Then we will have on next. Then we will have. And you heard you could have ah updated new head here also, we know it will be Kate Element, so you can check here. That is, uh and his kids didn't new had to call to current what we can do it in the letter. Also while reversing. And two more points which were even and Tito even Stevenage initially Nall and he twists the first of all. Let's write it in separately or tell you will be the head. It does not matter. We will anyway update this and what we have to do now This we will reuse this very well. We can have a separate current also or we can have a separate in order here. But the task is our main goal is to make current point to first know before starting the reversal. Current is pointing to head no while is greater than he called. Okay? Even implement our like So this is the main logic. And we have to reversing blocks off K. So I equal to zero. I let them k are you plus Plus, you can use for Liu by Luke whatever you prefer. So this will execute gay times. And here it will be simple list reversal record. So next equal toe current next and current next to Quito. Previous previously quality current current equal to next. Very simple. And this will wouldn't care times. And when this Liukin's the first time we will have this new head has millions. In that case, new head will become previous. But if you move it out here, this line is not required. No, for the first block till one will be empty. So naturally we haven't distinctive. Stephen is there, then even next equal to previous and did to next week or two Couldn't. So, what is t two t Tuesday? Uh, uglier Earlier It even so, whatever. Was. So if you see here once we're done with this part and we're starting here, so see easier current easier. We have reversed. We have just reverse this part so teetotal pointing here. And we're just adding this link even before starting the reversal. Because for the last part, this is only requirement and is not a malt loaf. Okay, because in the last part, twist here, so make its next point to current other way. If you don't add this link, this will be broken. This will stop here. So there's just required then, uh then in these not Martin Luther King. You can try playing with it. You will understand it better. And what else do we need to do now? Even will become detour. So whatever was to to is not even and he too is the first Nordoff the next block, which we're going to reverse since first nor becomes last note. So this is mad with 32. 32 will be current and we're resetting previous TUNEL and in minus equals K. And finally what we have to return. We have to return them. You heard. And this works for this case. Let's add a few more excuses. Looks heard for three. That's hard for one, and it passes for all so we can wear and submit. So it takes 16 minutes again we are faster than 82% of the users on memory here. So what is the time? Complexity. Here we are. Just a scanning this list twice once for getting the count. And next we're scanning first gay blocks the next give looks and so on. So it's often and we're not using any extra space narratives proposed meditative lentil the list and that was the requirement that we were doing lingered on Lee Constant extra memory . We could have done it recursive lee not reverse the first key part. And then whatever is the remaining list recursive lee call that function so that will again return the new head so make its next point so that we could have used rickerson also, but to, uh, Dickerson Stack can go upto in my queue times if we have to call this function for each kid block. So that's where they were not using rickerson here. If you call in that space, this tech space and we were not allowed to modify the values we have to actually move the notes. So this video is getting longer. You can convert it to job, are fighting. If you're using your fightin there should be straightforward conversion from sleeplessness to job are quite him. So I've learned here to you in the next movie. 25. Reorder Linked List: This is a singly linked list based problem. And in this we have to reorder the north of the list and we are not allowed to change the values. We are allowed to actually move those node, nodes. So if we have, let say list like 123. So it's not that if we want to let say we want to reverse it. So in that case we are not just copying the value and putting it here. We're actually moving the, this pointer here. So we have to actually move the knowledge and not devalued. And how do we need to move the list? Let's see an example. So let's say this is a ListNode is given to us. It's a singly linked list. And the results would be such that first MOOC will be one, its next will be the last node. So when we're picking from website one, we're picking from Wright State. So one fight. Then this left one comes here. One comes here. So next is two. And then it's next will be the one from right. Then you move this here, and you move this here. But you cannot move backward in the singly linked list. And this is the basic LinkedList concept. So after four, it should be three and it should be null. So number of nodes remains in, we just reorder them. That's why it's called the reorder, the list. And it's commonly asked in Facebook, Amazon, eBay by dams and if you want companies. So it looks like it poplar problem. So how can we do this? So we need one from the beginning and one from there. And so I will, I will start with a not so elegant solution. Then we will arrive on a much more elegant solution. So we will, we will do first, we will travel to this list and install the pointers in a stack. So we stored 123 for these other actual pointers. And now it's sages 5p. So once we have put it in the stack, we will start from here. So current will be here at the head, and then its next. So let's store Do, we will need to. So next off five is two. So we save this into a variable called next. Next equal to current next. This we can do. And currently Ginny's late to the head. This is heard, we are not changing it. And this will remain headed for the final list ons. So it's next we saved, so it's storing to the north corresponding to two. And then current's Next is equal to top of the stack. So this is stack S is not top. And then we also pop it. So five is gone. And currents next is this top. So what is the state? We have one, its next is pointing to and face next door in middle. So not Northern pointer changes and to each separate. So du is pointing to 33, is pointing to 44, is pointing to 55, is not pointing anywhere. So this is the state after this statement. Next, what we will do. Our current should move here at 5p. So this part is fine. Lays no, after one there will be five. So current equal to current next. You don't need to use this solution. I am just writing it. It will give you some practice. And then we will also see a better socialism. So stay tuned for that. So current node comes to five. And then five next to be 22, we had saved in the next variable. So current comes to five, and current and next is equals to next. And next was two. So what is the statement? Let me redraw it. Five's next is T2. And currently just delightfully, so what we can do, current equal to current next. So no current comes out to. And let me remove two from here. So this is one nitrogen in this what we did, we didn't one phi two. So this part is fine, late and current is again here. And the next of two is three. And it has not changed. This pointer, we never updated. So we have to just do the same thing on this part of the list. So at the end of this loop, we are again back to the original problem with the smaller list. So again, Next we will store that is three. So this temp1 next is three. And currents next equal to S dot dot. That is fought. So current was due, so it's next is null for. So next off. Two is four. And current equal to current next, so current comes here. And it's next is next, whatever we had saved. So that is three. And current comes here, actually. And then we will stop since we have added five nodes. So how many times we would pop it? So we will keep track of how many nodes are there. So there are five nodes, so we will do two panes. If we add six node, we will have them three times. So now we will stop and this Luby. And so what is the state one is pointing to? 55 is pointing to to do is pointing to food forest pointing to three, but three is again pointing to four. So this is the extracting that we need to take care of. So when this loop ends, guarantees pointing here. So at the end of this loop, what we will do current next equal to null, and that's it. So this is no null and we get the year. The complexity for this would be, you can see we don't to traverse the list 1-4, this building the stack and second foot or changing the pointers. So time complexity is often space complexities also often. But there is a better way we can get rid of the space time complexity. We cannot get rid off its expected. So you, you'll be looking. You can see that from the stack we're bopping half of the elements. That is, we are interested in the second half of the list. So in the second approach, what we will do, let's write, let's write it again. 12345. So we are interested in the last two elements. So if we reverse it, so let us reverse it. So we make it 123. And then these pointers we have to change phi four. So five, then four. So in the first part, first half, you see 123 occurring, seems sequence. That is in or in an order. But the later half occurs in reverse order. That is first 5p, then full than if you tried any other element. So if v reverse this part, then our job will be very simple. We just merge two lists one by one. So keep it as it is. And this reaching the Thisbe mic 5p, it points to 44, points to three. So we have reversed it. So now let us draw it in a different manner. We draw 12354 and it's also pointing to three and next of trees null. So this is after we reversed though later half. And how can we reverse it? Very simple. You start that slow and fast pointer concept. Slow pointer, point to slow, pointed at one's way, 1 and 1s 2p. And as soon as fast becomes null, North next door fast becomes null. We stop. So then slowly hair faster year, when slope comes here, fast comes here by two steps. Then slow comes here. And fast again jumps back to strip that is full. At this point we will stop since the next of fast is null. Then we know the middle of the list. So we will take this list. So just take this part of the list. So whatever is the slope pointer pointing to, reverse the list starting from there. And the reversal code is very simple. We will write that in the core. So after reversing, this will be the state. So now let's focus on this. So now what we will do, we will take two pointers. Let's call them N1 and N2. So how will get 5p? So we will reverse this part currently here, next year, previous is null, so it's next will be null. So 3s Next, we will make it none, whatever it is previous. So the way to reverses current next is radius. So whatever was the previous, we make it next. And then we will add once current, current equal to current next. And previous equal to so first previously will update previous equal to current and current equal to current next. So we will see that. So you must be familiar with reversing. The list is very simple. So now at the end, we will reach here and the current will become null, then we will stop. So previously will be pointing here when not before. So previous is pointing to the last node we will insulate into. So n one will be initialized to head into, will reinitialize to previous. And we have reversed it. This is the stick. So our job is very simple. What we will do. When next equals 22. So this is very clear evidence. So once Next is five, so this is denser. Once next should be flight. And after their next off, I should do so better store it in a variable. So this is initially is in part and this is we will doing at reasons. So MPs pointing to two, next one is fired. After that, what we need to do at the end of this activism visit B and one should be here and into sub here. So the problems will be exactly like before. So we move to next, and when equal to DMP, we are distorted in TMP. So N1 is Null here. Not what next? There is one, phi two. And here we should have 43. Come here. So let us do fall or DMP equal to N two dot next. So this force we have saved and after that into next equal to Five's next should be or two. So n one and n two equal to M p. So in two comes here. Now, M2 is here, in Venice, here. So this is the state after one nitrogen. So this part is no finalized and we have to just work on this part. So again, do the same thing. So it will be to, its next will be fought. And M2 will come here, and n will, will come, become null. So we can add a condition that if N two dot next is none, we stop. So let's write the code for this. We would like the court for Bordeaux that rooted in fact. So now we have written is pushed into the stack. If you have less than or equal to two nodes, and then we don't need to change anything. So if n less than equal to simply written, there is no reordering. We will need to do it in weight. So we pop elements from this tech. Or we can define this outside, since it will be done again and again. And what we had done for the last node, we set the next equal to none. So in the last part, this tree was pointing to four, so we had to do this. So this is the first holism and it will take off in the next, we will implement this one. So first let's run this. So this is an accepted and it takes 40 milliseconds. So let's implement the other one and we will compare if it takes list name on one. So in this, let's say the viscous if here it is not there or next of her denominator, then written in did not return anything, so just written. And then we'll wind up middle. So after that, what we will do, we initialize the current with slew net list. And we will need a temp variable where we will save the next pointers. You can also call it next. So we are just reversing the second part here. So this is the reversal part. So we have stored the next smell. The next of current should be previous. Whatever was the previous. Then we add one to the previous two next, so the previous four, the next node will be whatever its current node, previous equal to current. And then current should also move. But we obtained the current mixed. But before that we had already saved what was next of that. So current moves there, which is very simple, it will reverse the second half. Then we will do this final part needed merging of the two lists. One L1, first from first node, second node from second list, and so on. So we have restored the next of west and we will make the next often this 2n2 And the next of n closer b, this one DMP. So m2 next is BMP. We change this, we will lose track of the next of n2. So all we will stall that first. N1 looks at once it, we are done with N12 and when it becomes, it's next, that was DMP. Knowing DMP we store the next of m two. So we are using the same variable for what purpose you can use to also, but the work of DMPs donkey layer for this part. So here we are storing in to next. And then only we will change the next of n two. Otherwise we will lose. We will break the list. So we have a store next and then update its next to N1. And N2 becomes DMP. So these two parts may look very similar. The first 10-second part. And then end of this addressing 18 reason. We will find ways to nodes one from first list, one from second. And both N1 and N2 have advanced way one in both the corresponding lists. So time limit exceeded, we must be doing something wrong here. So some of the loops are not terminating. So this clearly is valued. Current equal to current seats would be DMP. Otherwise it will never terminate. And the solution is accepted. So it takes 28 millisecond for a little bit. Damn complexity is same. You can see much more improved Mingun envoy need for a percent. Although this can be a fluctuation also. That's right. Finally, we will do it in Python. And the Python.