1 00:00:00,660 --> 00:00:01,530 Hi everyone. 2 00:00:01,530 --> 00:00:04,290 So we have successfully coded the solution. 3 00:00:04,290 --> 00:00:10,320 Now let's quickly take a sample input and walk through the code that we've written to understand what's 4 00:00:10,320 --> 00:00:10,950 happening. 5 00:00:10,950 --> 00:00:11,460 Now. 6 00:00:11,460 --> 00:00:16,680 This part of the code is just written so that we can test the function that we are writing over here. 7 00:00:16,680 --> 00:00:17,160 Right. 8 00:00:17,160 --> 00:00:20,190 So this is a node class right. 9 00:00:20,190 --> 00:00:23,400 So using this we are creating a node with value one. 10 00:00:23,400 --> 00:00:30,240 And we are saying that the next next uh the pointer of this node is pointing to the node with value 11 00:00:30,240 --> 00:00:30,360 two. 12 00:00:30,390 --> 00:00:35,400 So one is pointing to two and two is pointing to three and three is pointing to four. 13 00:00:35,400 --> 00:00:38,640 So this part creates this singly linked list. 14 00:00:38,640 --> 00:00:44,610 And we are going to pass the head which is one, into the reverse linked list function which we have 15 00:00:44,610 --> 00:00:44,880 written. 16 00:00:44,880 --> 00:00:47,790 So we are going to pass this particular node over here. 17 00:00:47,790 --> 00:00:50,850 Now at this point previous is set to null. 18 00:00:50,850 --> 00:00:53,130 So I'm just calling previous as P. 19 00:00:53,130 --> 00:00:54,630 And there's nothing over here. 20 00:00:54,630 --> 00:00:58,200 So let's take this as null and current is set to the head. 21 00:00:58,200 --> 00:00:59,700 The head is one over here. 22 00:00:59,700 --> 00:01:01,080 So that's what we have done over here. 23 00:01:01,080 --> 00:01:01,830 Current is head. 24 00:01:01,830 --> 00:01:04,440 Now we are going to have this while loop right. 25 00:01:04,440 --> 00:01:06,000 And we are going to repeat this. 26 00:01:06,000 --> 00:01:12,060 As long as current is not equal to null or we will stop this when current reaches over here. 27 00:01:12,060 --> 00:01:17,130 Right when current reaches over here, it will be equal to null and we will stop the while loop. 28 00:01:17,130 --> 00:01:17,820 All right. 29 00:01:18,240 --> 00:01:19,710 Now previous is null. 30 00:01:19,710 --> 00:01:21,930 Current is the node one. 31 00:01:21,930 --> 00:01:29,490 Now we are inside the while loop and we define another uh pointer next which is pointing to current 32 00:01:29,490 --> 00:01:30,270 dot next right. 33 00:01:30,270 --> 00:01:31,740 So current dot next is two. 34 00:01:31,770 --> 00:01:33,300 So next is at two. 35 00:01:33,300 --> 00:01:35,190 Right now we have stored this. 36 00:01:35,190 --> 00:01:37,080 So it's safe to severe this connection. 37 00:01:37,080 --> 00:01:39,030 So we will break this connection. 38 00:01:39,030 --> 00:01:43,500 And we will make one point to previous or null right. 39 00:01:43,500 --> 00:01:47,490 We'll make this node point to previous which is what we're doing over here. 40 00:01:47,490 --> 00:01:49,770 Current dot next is equal to previous. 41 00:01:49,770 --> 00:01:52,260 And at this point previous is null right. 42 00:01:52,260 --> 00:01:54,720 So we are getting one pointing to null. 43 00:01:54,720 --> 00:01:56,160 So that's what we are getting over here. 44 00:01:56,160 --> 00:01:59,040 And then over here we are setting previous to current. 45 00:01:59,040 --> 00:02:00,630 So previous is moved over here. 46 00:02:00,630 --> 00:02:02,190 And current is set to next. 47 00:02:02,190 --> 00:02:03,630 So current will be moved over here. 48 00:02:03,630 --> 00:02:10,020 So we are moving previous and current and we are done with one iteration of the while loop. 49 00:02:10,020 --> 00:02:12,420 Now we are going to check again whether current is null. 50 00:02:12,420 --> 00:02:13,620 So current is not null. 51 00:02:13,620 --> 00:02:15,420 So we again do this right. 52 00:02:15,420 --> 00:02:17,100 So we will find next. 53 00:02:17,580 --> 00:02:19,470 And we keep doing this again and again. 54 00:02:19,470 --> 00:02:23,310 And we will do this till current reaches over here. 55 00:02:23,310 --> 00:02:23,610 Right. 56 00:02:23,610 --> 00:02:26,940 We'll do this loop till current reaches over here. 57 00:02:26,940 --> 00:02:31,170 So in the next loop we will have previous over here current over here. 58 00:02:31,170 --> 00:02:32,700 And we will have next over here. 59 00:02:32,700 --> 00:02:37,080 Then we will remove this connection and we will make current point to previous. 60 00:02:37,080 --> 00:02:37,260 Right. 61 00:02:37,260 --> 00:02:39,000 So we will make two point to one. 62 00:02:39,000 --> 00:02:42,450 So we'll get two pointing to one pointing to null. 63 00:02:42,450 --> 00:02:44,460 And then we'll add three over here. 64 00:02:44,460 --> 00:02:44,820 Right. 65 00:02:44,820 --> 00:02:47,310 We will again move previous current next. 66 00:02:47,310 --> 00:02:49,560 And we will make current point to previous. 67 00:02:49,560 --> 00:02:52,860 So we will have three pointing to two pointing to one pointing to null. 68 00:02:52,860 --> 00:02:58,050 And after that again we'll have four pointing to two pointing to three pointing to one. 69 00:02:58,050 --> 00:03:01,080 And at this point when we do current is next. 70 00:03:01,080 --> 00:03:01,890 Next would be null. 71 00:03:01,890 --> 00:03:02,100 Right? 72 00:03:02,100 --> 00:03:04,680 When current is over here, next is null. 73 00:03:04,680 --> 00:03:07,170 And then we over here we are doing current equal to next. 74 00:03:07,170 --> 00:03:08,580 So current will become null. 75 00:03:08,580 --> 00:03:13,290 And at this point the while loop stops and we just return previous right. 76 00:03:13,290 --> 00:03:18,540 Previous is this node over here which is the head of the reverse singly linked list. 77 00:03:18,540 --> 00:03:19,740 And that's our answer. 78 00:03:19,740 --> 00:03:21,300 So that's what we had to do. 79 00:03:21,300 --> 00:03:23,850 And we are able to successfully do it over here. 80 00:03:23,850 --> 00:03:31,560 And the time complexity of this solution is O of n, because we have to traverse the singly linked list 81 00:03:31,560 --> 00:03:32,370 one time. 82 00:03:32,370 --> 00:03:37,230 And the space complexity of this solution is O of one or constant space. 83 00:03:37,230 --> 00:03:39,930 Because we are not creating a new linked list. 84 00:03:39,930 --> 00:03:40,350 Right? 85 00:03:40,350 --> 00:03:40,620 We are. 86 00:03:40,620 --> 00:03:46,590 We are just having a few pointers and we are changing the direction, uh, in which existing nodes in 87 00:03:46,590 --> 00:03:48,120 the memory are pointing. 88 00:03:48,120 --> 00:03:50,010 And those are the input. 89 00:03:50,010 --> 00:03:50,700 That's the input. 90 00:03:50,700 --> 00:03:50,850 Right. 91 00:03:50,850 --> 00:03:52,890 So we are not using any extra space. 92 00:03:52,890 --> 00:03:56,730 So the space complexity of this solution is O of one.