• 15 hours ago
Transcript
00:00The next question we will talk about is find and remove nth node from end
00:04and we will solve this using iterative approach
00:07This is my question, I have asked many companies including Amazon, Adobe, Qualcomm, Flipkart and other companies
00:13This question is very famous because there are many approaches
00:16The approach I am going to discuss here is the most simple approach
00:20and I will solve this question within linear time complexity
00:24This means that I will give a link list in which I have to count from last to the nth
00:30node
00:30I will take an example
00:33I have a link list in which I have some data values and integer values stored
00:40I have data here, I have 1, 2, 3, 4, 5
00:44I am pointing next to my next value
00:46and I am pointing to the null
00:50This is my head
00:53If I have a value of nth node
00:55It means that I have to say that I have to delete n is equal to 3
00:59And the 3 is this is from end
01:01I have to delete last to the third node
01:04So what can I say?
01:06Last to this is
01:07If I start counting back to the third node
01:08This is my last to the first node
01:10This is my last to the second node
01:12This is my last to the third node
01:14This node
01:15This node
01:15I have to delete this node
01:17How can I delete this node?
01:19How can I delete this node?
01:19The process of deleting this node
01:21This is this
01:36What will I do?
01:52I have to delete this node
01:54This node
01:59I have to delete this node
02:10I have to delete this node
02:20This node
02:21I need to delete this node
02:22And the path
02:22I have to leave this node
02:23I have to travel
02:23And the path
02:23I have to travel
02:25This way
02:25I can travel backwards
02:27That is possible
02:28It is possible
02:29When I make the link list
02:30And I will reverse this node
02:33Then I delete this node
02:34And I will reverse it
02:37In this case
02:38This is possible
02:38But
02:40we will see a little bit of a simple way, in a simple way I will explain a little bit
02:44of logic
02:44if my node is nth, if the nth node needs to find out from end
02:50what can I say, if I find out from start that will be equal to my size
02:58minus n plus 1th node, like if my linked list is size 5
03:05and I have nth value 3, I have to find out my 3rd node
03:11so the last node comes to the third, starting node is size minus n plus 1
03:18i mean 3rd node, this is the first node, this is the second node, this is the third node
03:24so the last node comes to my nth node, it becomes size minus n plus 1th node
03:34this is the third node, this small thing I have derived
03:37how to derive it, I assumed that I have the size of the link list
03:41now what I have to do with the help of the size
03:44I will find out from start that node
03:46I can find out from start that node, I will run the loop
03:49until my index value is equal, I will increase in loop
03:53yes, I can't find out from last, nth
03:56but from start that node, size minus n plus 1th
03:59I can find out from start that node
04:01so I am going to do the same thing
04:02what will I do?
04:04what will I do?
04:04I will be able to calculate the size
04:05in fact, for my linked list, I always have size calculated
04:09if it is not, I can calculate it in my function
04:12what will I do?
04:14then, if I have to delete this node
04:17so I need this node
04:20or previous node
04:22why should I need previous node
04:24because previous node
04:25will point to next
04:26when I have to delete the node
04:29this node will automatically delete
04:31so I have to run a loop
04:33when will I run the loop?
04:35when will I start the value of 1
04:37I will not reach size minus n
04:40size minus n is this
04:42size minus n plus 1 is this
04:44I will go to size minus n
04:45because I have to change the previous node
04:47because I have to change the previous node
04:49it will automatically delete
04:50so I have to change the previous node
04:52I have to change the previous node
04:54I want to point to the next node
04:55to the deleted node
04:58so I will write code
05:00which will be easier to write
05:02within my linked list
05:03I am going to create a function
05:03public
05:06void
05:07delete
05:08init
05:09from
05:10end
05:11I will pass the value of n
05:13my initial values
05:14first
05:14my work will be to calculate
05:16size of my linked list
05:17size of the link list
05:18calculate
05:19here
05:20I have a parameter already
05:22made in beginning
05:23I have created my parameter
05:26but
05:28I am going to ask you so that
05:29you will participate in a contest
05:30or you will solve any other question
05:32on some platform
05:33going to a path
05:34we need to calculate size
05:35there
05:36then
05:37I am going to calculate the size
05:37calculate it and show it. I take a variable, int size is equal to 0, I write int size is
05:43equal to 0 and I take a temporary node, node temp is equal to head, until my temp is not
05:54equal to null.
05:58So what will I do? I will do temp next and size is equal to plus plus. So my size
06:08is calculated. As I have the size calculated, first of all, I will check that I have to delete my
06:15head.
06:16If in this case I have to delete my head, what will I do? If my n is equal to
06:24my size, last from n, i.e. head, the value of n is equal to size.
06:32If in this case I will be head next. And I will do return here. If I have to delete
06:40my head, what will I do?
06:41If I have to delete my head next. Or I can say this is my remove first operation. I have
06:48written the definition of remove first.
06:50What will I do in the rest of the cases? In the rest of the cases, I have to reach
06:54size minus n.
06:57So I will make an index, i is equal to 1 to equal. Who will I find out? Int index
07:03to find.
07:05Int index to find is my size minus n. So I will run a loop until i is less than
07:12index to find.
07:16What will I do every time? Where will I start from this loop? I will make another variable with previous,
07:23which will start with my head.
07:25My previous value will increase and increase. Until I, index to find, or previous, will not reach the actual previous.
07:33So I will do previous, previous next. And i will do plus plus.
07:38I will make another variable with previous previous. I will make another variable with previous previous.
07:45So I will make another variable with previous next. And here I will do return.
07:53Return. We will understand this slightly. I hope that I will understand that I will calculate the size.
08:00After that, this will be my corner case. If I have to delete the head, then I will not perform
08:05all the operations.
08:06Then I will know where to delete. Where to delete, I will create the head.next.
08:11This is basically my remove first operation. And I will do return.
08:15In the rest of the cases, I will reach the index to the size minus n.
08:20That means, until I reach that index, which is my node to delete, is just the earlier index.
08:25The way to reach that is, I will run the loop.
08:28Just like I reached there, previous.next is equal to previous.next.next.
08:32What does this mean to say the last line? If I have this link list, one, two, three, four, five.
08:44And this is all pointing. This is my null. If my head is here.
08:51If I have n given 3, then what can I say? My size minus n will be equal to 2.
08:57Which is equal to 5 minus 2. Size here is equal to 5.
09:01Now I will find out the 2th node. This is my i is equal to 1th node. This is my
09:06i is equal to 2th node.
09:07This is my previous node. This will become my previous node. And I will delete it. I will delete it.
09:14Now I will delete the node from the previous node. I will use previous node.
09:19So I have this line on there. Previous next is equal to previous next.
09:26Next. What does this mean to say? Previous next is next. This is my previous node.
09:34This is next. This is next. This is also next. I am talking about this node.
09:39So what do I have to do? This node is assigned its value to previous next.
09:45This means previous next is now directly point to this value.
09:50This I have formed a connection here. This connection formed. This connection formed.
09:54So this connection broke. And this connection broke.
09:57So now this node will automatically delete. This process of deletion will be automatic.
10:03How will it be automatic? Garbage collector will automatically delete it.
10:06Because now it will not point to this point.
10:09My previous node will directly point to next.
10:12So now my final link list will come. How will the link list look?
10:15How will it look like? First of all, 1 will come. Then 2 will come.
10:19Then 4 will come. Then 5 will come.
10:22So now let's run this again.
10:25I have written my entire code.
10:27For which reason?
10:27I am going to delete nth from end.
10:29Now what am I going to do?
10:31In the main function, I have created the link list.
10:341, 2, 3, 4, 5.
10:35From there I will delete it.
10:40Delete from end.
10:44Last say, I will delete the third node.
10:46And then I will print.
10:49Save and run.
10:52Last say, third node.
10:53This is the first node.
10:55This is the second node.
10:56This is the third node.
10:57This is the third node.
10:57So my 3 will automatically delete.
10:59And now my link list is 1, 2, 4 and 5.
11:02Where now I have 5 points to null.
11:04So if I want to delete the last node,
11:07I will remove the index from the beginning.
11:09And then I will directly join the previous node.
11:13So this is the deletion from my end in a link list.
11:16Iibe пят.
11:17And then that will keep me perfect and manifest.