2.18 Reverse a Circular Linked List | Data Structure Tutorials

Now see as we have discussed how to reverse a singly linked list right. What reverse means? Suppose I have four node in the list right and in circular link list the last node will contain address of the first node and we are maintaining only the tail pointer. Tail pointer is containing address of the last node right. So now what reversing means we are not going to swap these nodes right. What we actually do we are going to reverse these links. See here each node is containing address of the next node right but after reversing what it should look like this node would contain address of the previous node. We are going to reverse this link right means now see this node is containing address of the next next node that is 150 but after reversing this node would contain address this should contain address of the previous node that is here we will store 500 right this node also contain address of the previous node that is we are going to reverse this link we are going to reverse this link so see it is almost same as reversing a singly link list that we have already discussed only difference is what now in this case last node is containing address of the first node. But after reversing obviously we are going to reverse this link also. So now this node is containing address of the this node. Now we are going to reverse this. Now this node should contain address of this node that is this node now should contain 600. So now we are going to reverse this link because after reversing this should be the last node. And one more thing now after reversing tail would point here. Right? So when you will display the link list after reversing then then it should print minus3 6 1 and 7. Now for this how you will do this reverse operation. See suppose at some point of time I have a pointer to this node. Right? Obviously we are going to take some pointers extra pointers because we cannot move this tail right. So for reversing we are going to traverse the link this list and with the traversing only we are going to reverse these links. Right? So now suppose I have a pointer temp pointing to this node. Now in this node I should store what value of address of this node for reversing this link. Right? So suppose I have stored temp of next equal to from where I can get this address in tail I have this address. So temp of next equal to tail. It means here I have stored what rather than this I have 600 now. So now you can say this link is no more. Now this node is pointing to this node. Okay. Fine. But now this link is no more than how you will reach till this node because obviously we are going to reverse this link also. This link also right? We need to reverse all the links. So now suppose by applying some logic I'll tell you that logic we we have reached till here. We have moved our temp here right. We will discuss that logic also when we will write that code. Now in temp of next I will store what this node address of this node address of previous node. So we have to maintain address of this node also because if you remove temp here then how you will from where you can get this address 500 because we have only one pointer left but tail pointer is pointing to the last node. Right? So now you have to maintain one another pointer. Suppose I'm taking previous pointer. So before moving temp forward we are going to set this previous also. Now in previous you have 500. So we can write temp of next is equal to previous that is also fine. Now you have broken this link. And now here I have 500. So this is now pointing to this node. Right? Now how you you will move here. So you need some extra pointer. One more pointers. So basically three pointers we need here. Fine. What you can do before setting this before breaking this link before setting here 500 what you can do we can set suppose a pointer next node third pointer to this node and how you can do in next node next we can write next node is equal to temp of next that is 150. So here I have in next node we will have 150. So this will point to here. So now you can break this link. You can set temp of next is equal to previous. And we have a pointer to next node also. So we can reach till this node. Right? After that we can move this temp. Then we will move this previous also. And the next node become this one. And now we are going to move till this node. Right? Till we reach here till the last node. It means we are going to take basically three pointers here. rather than temp I'm taking what current you can take any name current previous and next node right so see how you will write down the code for this thing so as you can see we have declared three pointers preview pointer current and next node and these pointers are pointer to node because these are containing address of the node so here I'm taking str node right this thing I guess you already know that user defined data type the two parts are there of this node data part and one is next pointer this will contain address of the next node if you have maintained in only the tail pointer right so this thing we this is what the global part this we are going to use in all the functions if you call that create function display function or this function so this uh thing I'm going to write globally out of all these function and out of main function you can say after header files directly right after that you can define this reverse function now see we have taken three pointers now for reverse obviously we are going to traverse the link so for traversing we need one pointer. So I'm taking that current pointer that is main pointer. These previous and next node you can say these are supportive pointers of this current. One is containing one is storing address of previous node and this will contain address of the next node. Right? So first of all what you will do now we are going to start from head node. Now from the first node we are going to start the traversing. So we are we are not having any head pointer. So how you can come to know that the which node is the first node. So tail of next this will always contain address of the first node. So how we can do current is equal to tail of next. It means now current is pointing to this node. In tail next we have 500 in current. Now we will store 500. So now as you can see this current is pointing to this node that is to the first node. Right? Now you can check if tail is equal to zero. It means list is empty. You cannot reverse the list. Right? So you can uh after this you can write down this condition also. If tail equal to equal to zero it means list is empty you can print this thing or if you want to print that thing also that if suppose in list we have only one node. How you can check that thing? We have discussed when we were discussing how to delete node from the circular link list. Right? If suppose only one node is there then tail would point here and current would point here. Right? And this node would contain address of itself that is here also 500 here also 500. So you can check else if that tail of next is equal to is equal to tail or you can say current of next is equal to is equal to current right in that case you can directly call that display function or you can say that there is only one node in the list and only this if seven is the node then seven would be printing after display after reversing the list. Else we are having four nodes. Now, now see what is the situation. Now how you will write this thing here? I will write a while loop while this current because for traversing we are using this current node. When you will stop here right when this current becomes when current will point here it means current is pointing to the tail node it means current becomes equal to tail. So we are going to move till current becomes until current becomes tail. So current not equal to tail till then we are going to move this current right. So before moving this current obviously first of all we are going to set our previous pointer right. So here you will write this pre is equal to current. Now this pre is containing 500. So now this is pointing to this node right now only difference in this case is now it should have address of the this node right because we are going to reverse this link also right but at starting we will not reverse this link we we are going to reverse this link at last fine because if in while loop only you will write this statement now I can write previous of next here I want to store address of this thing that is 600 so here I can Write previous of next is equal to tail. Right? So if you write that statement in while loop then so when after some iteration current would point to this node. In that case previous would point to this node. Right? Because this is the previous node. Now again that condition would be executed means previous of next is equal to tail. So previous of next is this this pointer now. So here you will store address of 600. So now this node would point to this node but that we don't want. And after that previous would be this one. Current would be this one. In that case also previous next is equal to tail. So again and again that line would be executed. So we don't want that thing. So first of all we are not going to reverse this link. We are going to reverse what? Next links. It means we are not going to change this value. It means we are not going to break this link. Right? So this link is still there. We are going to break this link. First of all we are going to uh store here what address of the previous node that is 500. Fine. And this link would be there. Still this link link would be there at last we will update this pointer. So now here obviously we we will move this current now. So here you will write current is equal to So now in current what do we need to store the value of this this this node because we are going to move this current. Now current is pointing to this after that current will point to this node that is 200. Right? So now here how we can store this 200 in current. See now here you need to set this next node pointer also. So see at starting we have set current is equal to tail next. So after this line after this line before this if statement what you will write what you will write you will set next node also next node equal to current of next. It means we have set both current and next node pointer. Now what is current of next? Current of next that is 200. So here now I have 200. So now this is pointing to this node. Right? So we have set both pointers at starting current and next node. After that you will write this if condition. If tail equal to equal to zero. Here you can print list as empty. Right? And in else part you will write this while loop. Now see in current what you will store address of this node. From where you can get address of this node that is next node is containing this node. Address of this node. So now current is having 200. Right? So now current is pointing to this node. Fine. Now we have previous we have set previous pointer also. Current also we have right. So now we can update this part. Here you will store address of previous node for reversing that is 500. So here what I can write? How you can access this part? Current is equal to sorry current of next equal to how you can access this part current of next equal to pre whatever the value in previous node right so now see pre have 500 so here we have 500 now this node is pointing to this node this link is no more now so now see the problem is next node is also pointing to this node now how you can reach till this node So this thing you need to take care you will you need to write which line first. So first before updating this we will move this next node in next node you want to store 150 from where I can get 150 here before updating here I was 150 I was having 150 right. So here you can write before this line next node equal to current of next current next means here before updating 150 was there. So now current node is pointing to this node right and now you can update this. Now current of next is equal to previous that is 500. Now you can break this link. There is no problem because we have already set a pointer to next node. Right? So now we will we are going to repeat these steps till here. See again while loop current not equal to tail current is 200 tail is 600. So that is fine condition is true again we will enter into this loop. Now previous is equal to current that is in previous we will store 200. So now previous is pointing to this node. Right? Now we will move this current. Current is equal to next node. In next node we have 150. So in current we have 150. Now current is pointing to this node. Right. Again we will move now next node should point here. Next node is equal to current of next current of next. Current is pointing to this node. So current next is 600. So in next node we have 600. So now next node is pointing to this node. So now we have set three links. Now you can update this value. So now here see how you will access this part. Link to this node is current of only current is pointing to this node. So current of next equal to previous. In previous you have 200. So here you will store 200. So see what address of previous node is 200. So now this is pointing to this node. Right? Again current is not null. Sorry tail. Current is 150. Tail is 600. So condition is true. We are going to enter into this loop again. See previous is equal to current. So here we will store now whatever the value in current that is 150. Right? So now you can see previous is pointing to this node. We will move this current. Current is equal to next node. So here we will store 600 right. So now current node is this one. And now next node is next node equal to current next. Now in current of next we have 500. So in next node we will store 500. It means you can see next node is containing address 500. That is now this next node. This next node would point to this node right to the first node. Fine. Current of next current is pointing to this node. Current of next is equal to previous. In previous we have 150. So here I will store 150. So it means now 150. This is pointing to this node. Right? So this link was no more. Now 150. So this link has been broken now. Right? Now we need to set this link. See we have set all the links. Now you can see say current not equal to tail. Now current is 600. Tail is also 600. So this condition is not true. So we are not going to enter into while loop. Fine. So now you need to update two things. Now we will set this pointer. See this node is the last node now. So this node should contain address of this node. Now fine because this will be the first node that is 600. Now how you can access this node pointer to this node is next node. Right? So here what you can write in next node next you will store address of this node that is 600 and we can we we already know the last address sorry the address of last node is always in tail pointer. So here I can write tail it means next node next here I'm storing 600. So now as you can see this is pointing to this node. Remaining one thing is what you have to move this tail. Now in tail tail should point to this node right. So in tail we want to store 500. So how you can get this 500? See po pointed to this link is next node. So next node is containing 500. So in tail I can store whatever the value in next node. Fine. So now in tail we have 500. So tail is pointing to this node. Right? As you can see we have reversed all the links as well as tail is pointing to this node. And now when you will display when you will call that display function then what the value should be printed minus 3 6 1 and 7. So this is how you can reverse a circular linked list. See after reversing and this link is also there not there now fine. So this is I guess same as reversing of a single link list only the simple the difference is what here the last node will contain address of the next sorry the first node right. So you have to take care of that link also and that link we will update in the last. So after this you can write void main function. In that main function you can first of all create this link list. You can call that create clen display function. Right? Then output would be before reversing 7 1 6 and 3. Then you can call reverse function and after that again you can call display function. So after that output would be minus 3 6 1 and 7. Right? So in next video we will see the implementation of a doubly circular link list. See, it was what? A singly circular linked list. Fine. So, I'll see you in the next video. Till then, bye-bye.