- 15 hours ago
Transcript
00:00Next question which we will do is to reverse a linked list
00:03This question is a very classical question
00:05and a very important question
00:08We have to understand the logic and the code
00:12What are we going to do?
00:14We are going to reverse a linked list and use
00:17Iterative approach
00:19If my linked list looks like this
00:231,2,3,4,5
00:25and this is pointing to null
00:28After reverse it will be something like this
00:32Now I am pointing to null
00:34If this node was my head
00:36then it will become my head
00:37This process is called reversing a linked list
00:42We will not use extra space
00:45We will reverse it in the same node
00:48First, let's understand the reverse process
00:51The reverse process is a 4 step process
00:53and it is very simple
00:55In fact, I will advise you that
00:57you will remember the same process
00:58We will remember the same process
01:01I will imagine that
01:03if I have nodes in this way
01:05I think that data stored 1
01:08data stored 2
01:10and this node stored 3
01:12This is my next point
01:14This is my next point
01:16This is my next point
01:19This is my next point
01:23I will reverse it in the same way
01:23I have no head
01:24This is not a linked list
01:26This is not a linked list
01:27This is not a null
01:28This is not a linked list
01:29It is also a linked list
01:30Let's say that
01:31I have to reverse this 2
01:33I need 3 variables
01:35First, I need 3 variables
01:37I need 3 variables
01:38First, I need the current variable
01:41One will be my previous variable
01:43One will be my next variable
01:44One will be my next variable
01:45Current, which I am talking about
01:47and I need to reverse it
01:49Previous, which I am talking about
01:50Before current
01:51Next, which I am talking about
01:52Next, which I am talking about
01:58The first thing I have to do is
02:09To change, from current
02:09First, in fact
02:10In fact, what is my process
02:12In fact, its the first step
02:14In fact, the first step is
02:14is the next step
02:15What I am talking about
02:16What is my next?
02:17My next is current
02:18It will be current
02:20We will always be current
02:21The previous current
02:22is already left
02:23Second, I should make the next
02:26one of the current
02:26We will make the next
02:27Close, which he was pointing to the next
02:29I will remove the next
02:30I will point it backwards
02:33So, current
02:34Next
02:35Now, your previous我
02:36will point over
02:38In fact, this which is my previous next, this is not the current point because I have already changed it.
02:45So, it will point where it will point. I have only previous value, current value and next value.
02:51What is current next? This current next was pointing before. Now, I have pointed it to previous.
02:56So, now it is connected. Now, what can I do in the third step?
03:00What can I do in the third step? I can do this in the third step. Now, I have carried
03:04this link to the back.
03:06I have linked it to the back. It means I have reversed it. It is very easy to reverse it.
03:11It means you have previous previous value. Now, I have to increase the previous value.
03:17Now, my previous value will come to current and my current value will come to next.
03:25It will come to next value. Now, these variables will change a little bit.
03:30Let's assume that there was another node here.
03:33For n. And this was pointing to null. Now, what will happen?
03:38Previous is equal to current. It means that previous is here.
03:44And previous is here. And current is equal to next. It means that next is here.
03:54And current is here. Now, I will repeat this process. How will I repeat this process?
04:00First of all, next is equal to current.next. So, this is my next.
04:05After that, I will point the current next to previous. Now, my current is this.
04:10Now, there is no point here. It is only next to the next. But next will point the previous.
04:15I will point the current value. So, this link is here. Now, I will put this link here.
04:20After that, I will store the current value in previous.
04:23I will store the current value again. I think that there was another node.
04:28There was another node. Here is data 5. Here is next. Now, what will I do?
04:33And the previous point is, I want to create current value.
04:36I will store current value. I will place current value here.
04:41I will place current value here. I will place previous value here.
04:44the next step is to create the current
04:46I will create the current and this will be my current
04:52now I have to repeat it again
04:56step 1 is next is equal to current
04:58second step is to point the current and previous
05:04so this will be removed from here and
05:06now my node is next
05:10point the current here
05:12third step is to create the previous
05:14so remove it and I will come here
05:17the previous step is to create the current
05:20next step is to create the current
05:21so the next will be removed from here
05:22and this will be my current
05:24so what I noticed is that
05:274 steps have been noticed
05:28first I have to create next
05:31then I have to point the current
05:33next to previous
05:34this is my actual reverse step
05:37then I will update the previous
05:38and create the current
05:40because today I will talk about
05:42the previous step
05:44then I will create the next
05:46for the next step
05:48I will repeat these steps
05:50when I will repeat them
05:52until I will repeat them
05:54until my current value
05:56while my current
05:58is not equal to null
06:01until my current value is not null
06:04until I will repeat them
06:05until I will repeat them
06:05in fact if I am pointing the null value
06:08here I am pointing the null value
06:09so if I am pointing the point here
06:10then next will be next
06:13that will be next
06:15that will be null
06:16then I will create the next
06:18so this will be removed from here
06:21and next will point here
06:24now my step is to create the previous
06:26current
06:27so here my previous will come
06:29and because of this step
06:32my next will be removed from here
06:34and this will become my current
06:36so now I will leave the loop
06:37because the current is finally equal
06:39and what I have done here
06:42what I have done here
06:43I have also had another link
06:43what I have done here
06:44what I have done here
06:45what I have done here
06:45I have done here
06:47I have taken the previous node
06:49and made the previous node
06:51meaning it is attached from the back
06:54so this is my reverse step
06:56so this will be my whole linked list
06:59that will be totally reversed
07:00I have to take a current
07:01which I will initialize with the head
07:03and I have to take a previous node
07:04which I will initialize with the head
07:07and how I will start things
07:08I will start things
07:08in these 4 steps
07:09I will start things
07:11so now I will write code
07:12I will create a function
07:13in my code
07:15public
07:16void
07:17reverse
07:20first of all I have to do
07:223 variables
07:23which are 3 variables
07:241 previous
07:251 current
07:261 next
07:26so first of all I will create previous
07:29in the beginning
07:30what will the previous
07:31what will it be?
07:32null
07:32because now the next
07:34next
07:35point
07:36the next
07:37value
07:37points
07:38so this is the link list
07:39further
07:40but what is the first node
07:42what is the first node
07:42that is the first node
07:44always null
07:44meaning the first node
07:45does not happen
07:46what is the node
07:47current
07:48what will it be?
07:50it will become my head
07:51in fact
07:52I will change the tail
07:54the tail
07:55that is the last node
07:56but because I am
07:57reverse the linked list
07:57I will reverse
07:58so now the head
07:59will become my tail
08:00so here I can write
08:01current is also equal to
08:03now my tail
08:04so my head value
08:06also stored in my tail
08:06and my current
08:07also stored in my tail
08:08always the assignment
08:10in Java
08:11is right to left
08:13so first the head value
08:14is assigned in tail
08:15then the tail value
08:16is assigned in current
08:17so now the tail
08:18I have updated
08:19that it will be the head
08:21third node
08:22is next
08:23we will not keep next
08:25I will not initialize
08:27I will not initialize
08:27next
08:27I will always initialize
08:29now I will write
08:30while loop
08:31while
08:31until my current
08:32is not equal to my null
08:34I know
08:35while loop
08:35there are 4 steps
08:36in fact
08:37reverse
08:37this is the best way
08:40remember
08:403 variables
08:424 steps
08:423 variables
08:43previous current
08:44next
08:454 steps
08:48next
08:54is now equal to my
08:56previous
08:56third step
08:57previous
08:58becomes current
08:59becomes current
08:59fourth step
09:00next
09:02current
09:02becomes my
09:03next
09:04we have written
09:04these 4 steps
09:05and the whole link list
09:08is reversed
09:09last
09:09I will update
09:10my head node
09:11so what will I do
09:13in the head
09:13I will create
09:14my previous
09:15equal
09:16because the current
09:17is null
09:17since the current
09:18was the first node
09:19now it is my head node
09:20so head becomes my
09:22previous
09:23let's do this
09:24save
09:24I have written the whole
09:25code of reverse
09:27now I will reverse
09:28this 1,2,3,4,5
09:29I will reverse
09:30link list.reverse
09:33and now I will print
09:34this again
09:36let's do this
09:36save and run
09:40first my link list
09:411,2,3,4,5
09:42and then 5
09:43points
09:43now my link list
09:45is 5,4,3,2,1
09:46which is now
09:471 point
09:48and now 5
09:49is my head
09:50and 1
09:51is my tail
09:52so we will reverse
09:53this way
09:55reverse
09:56and reverse
09:56time complexity
09:57turns out
09:59to be
09:59O of N
10:00what do we need
10:00to reverse
10:00what do we need
10:02to reverse
10:023 variables
10:03and we need
10:034 steps
10:05we write in the
10:06while loop
10:07and we keep
10:10assigning our
10:11right values
10:11going to
10:11in
10:12to be