1
00:00:00,620 --> 00:00:01,670
Hi everyone.

2
00:00:01,670 --> 00:00:07,400
In this video, let's think through and find a way in which we can solve this question.

3
00:00:07,400 --> 00:00:09,620
Now let's say that this is the input given.

4
00:00:09,620 --> 00:00:13,640
So the input is the head of this singly linked list which is node one.

5
00:00:13,640 --> 00:00:17,030
And that's pointing to node two which is pointing to node three.

6
00:00:17,030 --> 00:00:18,620
And that's pointing to node four.

7
00:00:18,620 --> 00:00:20,090
And that is pointing to null.

8
00:00:20,150 --> 00:00:22,340
Now let's have a pointer.

9
00:00:22,340 --> 00:00:25,610
And let's set the pointer to the input that we received.

10
00:00:25,610 --> 00:00:26,960
Let's call it current.

11
00:00:26,960 --> 00:00:28,490
Or let me just write cur.

12
00:00:28,520 --> 00:00:29,090
All right.

13
00:00:29,090 --> 00:00:32,330
Now before cur we'll have a previous right.

14
00:00:32,330 --> 00:00:33,980
So let's have previous over here.

15
00:00:33,980 --> 00:00:38,690
And initially this points to null because there is nothing over here right now.

16
00:00:38,690 --> 00:00:43,220
Try to visualize what we are trying to achieve right now over here.

17
00:00:43,850 --> 00:00:45,980
If we just take these two right?

18
00:00:45,980 --> 00:00:50,900
Currently one is pointing to two, but in the ideal output in the output that we want.

19
00:00:50,900 --> 00:00:54,950
Let's quickly write that over here, four will be the new head that will point to two.

20
00:00:54,980 --> 00:00:56,390
That will point to three.

21
00:00:56,390 --> 00:00:56,780
Sorry.

22
00:00:56,780 --> 00:00:58,220
That will point to three over here.

23
00:00:58,220 --> 00:00:59,450
This will point to two.

24
00:00:59,480 --> 00:01:00,620
This will point to one.

25
00:01:00,620 --> 00:01:01,730
This will point to null.

26
00:01:02,950 --> 00:01:09,760
Now we can see that in the input one is pointing to two, but in the output we want one to point to

27
00:01:09,760 --> 00:01:10,390
null, right.

28
00:01:10,390 --> 00:01:13,840
So we are actually trying to change the direction in which this point.

29
00:01:13,840 --> 00:01:16,480
So we want this to point in this direction.

30
00:01:16,480 --> 00:01:20,470
Similarly we can see that two is pointing to three right over here.

31
00:01:21,720 --> 00:01:23,040
Oh, so this is four.

32
00:01:23,070 --> 00:01:24,240
This is three.

33
00:01:24,330 --> 00:01:25,710
Two is pointing to one.

34
00:01:25,710 --> 00:01:25,980
All right.

35
00:01:25,980 --> 00:01:27,420
So two is pointing to one.

36
00:01:27,420 --> 00:01:30,240
Now in the input two is pointing to three.

37
00:01:30,240 --> 00:01:32,160
But we want two to point to one.

38
00:01:32,160 --> 00:01:34,230
So we want to change this direction right.

39
00:01:34,230 --> 00:01:35,490
So that's what we want to do.

40
00:01:35,490 --> 00:01:35,820
All right.

41
00:01:35,820 --> 00:01:39,900
So basically if we say that this is next this is current.

42
00:01:39,900 --> 00:01:41,790
And let's say this is next.

43
00:01:41,820 --> 00:01:46,080
Now currently in the input what's happening is current is pointing to next.

44
00:01:46,080 --> 00:01:49,320
But we want to change that and make current point to previous.

45
00:01:49,320 --> 00:01:52,020
So that is basically what we are trying to do.

46
00:01:52,020 --> 00:01:54,900
Now let me make some space over here and clean this up a bit.

47
00:01:55,170 --> 00:01:55,470
Right.

48
00:01:55,470 --> 00:02:01,140
So this is just for our understanding now we have understood that what we are trying to achieve is that

49
00:02:01,140 --> 00:02:03,270
currently current is pointing to next.

50
00:02:03,270 --> 00:02:06,210
We want to change that and make current point to previous.

51
00:02:06,210 --> 00:02:07,710
So this is what we are trying to do.

52
00:02:07,710 --> 00:02:10,860
Now let's think of a method by which we can do this.

53
00:02:11,100 --> 00:02:12,480
All right now.

54
00:02:13,600 --> 00:02:16,900
Over here we have current which is the input.

55
00:02:16,900 --> 00:02:17,800
Let me again repeat.

56
00:02:17,800 --> 00:02:19,180
We have current which is the input.

57
00:02:19,180 --> 00:02:22,330
And we have initialized previous to null.

58
00:02:22,360 --> 00:02:28,600
Now we cannot simply just remove this connection and make one point to null right in the output.

59
00:02:28,600 --> 00:02:31,270
We have seen that one has to point to null, right?

60
00:02:31,270 --> 00:02:34,420
Similarly two has to point to one, etc., right?

61
00:02:34,420 --> 00:02:36,400
So that that was the output that we wanted.

62
00:02:36,400 --> 00:02:42,730
Now we cannot simply disconnect this connection and make the next node of one to be null.

63
00:02:42,730 --> 00:02:43,210
Why is that?

64
00:02:43,210 --> 00:02:48,220
So if we do that, we won't be able to access any of these remaining nodes right?

65
00:02:48,220 --> 00:02:54,310
In the singly linked list, the only way to access the remaining nodes is using the dot next right function.

66
00:02:54,310 --> 00:02:54,490
Right.

67
00:02:54,490 --> 00:02:58,780
So we have to use one dot next to get to this two dot, next to get to this, etc..

68
00:02:58,780 --> 00:02:59,050
Right?

69
00:02:59,050 --> 00:03:02,590
So without storing it we cannot see where this connection.

70
00:03:02,590 --> 00:03:10,000
But at this point we have next over here we have created, we have created a new pointer next and we

71
00:03:10,000 --> 00:03:12,040
have made next point to two.

72
00:03:12,040 --> 00:03:12,400
Right.

73
00:03:12,400 --> 00:03:15,160
So yes, we can access two at this point.

74
00:03:15,970 --> 00:03:18,880
So because we have next, we are in a safe position.

75
00:03:18,880 --> 00:03:21,190
We can disconnect this connection.

76
00:03:21,190 --> 00:03:21,580
Right.

77
00:03:21,580 --> 00:03:27,430
So we are going to remove this connection and we are going to connect it to previous.

78
00:03:27,610 --> 00:03:29,170
So previous is null right.

79
00:03:29,170 --> 00:03:31,090
So we are getting this part over here.

80
00:03:31,090 --> 00:03:33,850
That is one is now pointing to null.

81
00:03:34,300 --> 00:03:34,690
All right.

82
00:03:34,690 --> 00:03:36,520
So we have achieved this much.

83
00:03:36,520 --> 00:03:38,500
Now let me clean this up over here.

84
00:03:38,500 --> 00:03:43,360
Now what we do what we do next is just the repetition of this.

85
00:03:43,360 --> 00:03:43,780
Right.

86
00:03:43,780 --> 00:03:47,500
We are going to move all these three one step ahead.

87
00:03:47,500 --> 00:03:51,880
So what is going to happen is we are going to set previous to current.

88
00:03:51,880 --> 00:03:53,170
So current is one right.

89
00:03:53,170 --> 00:03:55,000
So we are going to set previous to current.

90
00:03:55,000 --> 00:03:59,080
So previous comes over here and we are going to set current to next.

91
00:03:59,080 --> 00:04:00,880
So current will come over here.

92
00:04:01,000 --> 00:04:01,600
All right.

93
00:04:02,370 --> 00:04:06,720
And if current is over here, then next would be the next value, which is over here.

94
00:04:06,870 --> 00:04:07,380
All right.

95
00:04:07,410 --> 00:04:11,160
Now we have current at two previous is this part over here.

96
00:04:11,160 --> 00:04:17,310
And all we need to do is we just need to make this current point to previous again, which is the same

97
00:04:17,310 --> 00:04:18,270
thing that we did over here.

98
00:04:18,270 --> 00:04:18,660
Right.

99
00:04:18,660 --> 00:04:21,120
Again, we need to make this current point to previous.

100
00:04:21,120 --> 00:04:24,030
And we can severe or disconnect this connection.

101
00:04:24,030 --> 00:04:27,330
And that's safe to do because we have stored this over here.

102
00:04:27,330 --> 00:04:27,570
Right.

103
00:04:27,570 --> 00:04:29,700
So we can access the remaining part.

104
00:04:29,700 --> 00:04:33,180
It's not that we are losing the remaining part of the singly linked list.

105
00:04:33,180 --> 00:04:35,130
So we make two point to previous.

106
00:04:35,130 --> 00:04:38,190
Now previous is one and that is pointing to null.

107
00:04:38,190 --> 00:04:43,200
Now when we make two point to previous we get two, one and null right?

108
00:04:43,200 --> 00:04:44,880
So two is pointing to previous.

109
00:04:44,880 --> 00:04:47,580
Now we repeat this whole process again.

110
00:04:47,580 --> 00:04:53,760
We move previous to the next position, we move current to the next position, and when current is in

111
00:04:53,760 --> 00:04:55,710
the next position, next is current dot next.

112
00:04:55,710 --> 00:04:57,210
So that also moves right.

113
00:04:57,210 --> 00:05:02,190
So previous comes to current and current comes to the previous next right.

114
00:05:02,190 --> 00:05:05,280
What was previously next becomes current at this point.

115
00:05:05,280 --> 00:05:06,750
So we move this.

116
00:05:06,750 --> 00:05:11,580
Now what we need to do is we need to store the next value before removing this connection.

117
00:05:11,580 --> 00:05:13,770
We need to store the next node.

118
00:05:13,770 --> 00:05:15,480
So next becomes four.

119
00:05:15,480 --> 00:05:22,050
And after that we can safely disconnect this connection and make current which is three point to previous.

120
00:05:22,560 --> 00:05:28,830
Now when current points to previous, previous is two right and two is pointing to one and one is pointing

121
00:05:28,860 --> 00:05:29,400
to null.

122
00:05:29,400 --> 00:05:32,340
Now current which is three is pointing to previous.

123
00:05:32,340 --> 00:05:36,330
So we get three pointing to two and two points to one.

124
00:05:36,330 --> 00:05:37,380
And that points to null.

125
00:05:37,380 --> 00:05:39,000
So we have got this much right.

126
00:05:39,000 --> 00:05:41,760
And again we repeat the whole process.

127
00:05:41,760 --> 00:05:47,280
We move previous to the next place that is the current over here becomes previous.

128
00:05:47,280 --> 00:05:48,780
So we have previous over here.

129
00:05:48,780 --> 00:05:50,940
And what was next becomes current.

130
00:05:50,940 --> 00:05:52,470
So current is over here right.

131
00:05:52,470 --> 00:05:54,900
And next is the next value after current.

132
00:05:54,900 --> 00:05:56,190
So we get next over here.

133
00:05:56,280 --> 00:05:58,320
So we have these three again.

134
00:05:58,320 --> 00:05:59,610
So next is stored.

135
00:05:59,610 --> 00:06:03,480
So there is no problem in severing this connection even if there was a node over here.

136
00:06:03,480 --> 00:06:03,720
Right.

137
00:06:03,720 --> 00:06:06,600
So again we are we are thinking of a method of doing it right.

138
00:06:06,600 --> 00:06:09,420
So now we have stored whatever is next.

139
00:06:09,810 --> 00:06:13,710
Now we can see we have this connection and we make current point to previous.

140
00:06:13,710 --> 00:06:16,410
So four is pointing to three which is previous.

141
00:06:16,410 --> 00:06:21,750
So four is pointing to three and three is pointing to two, two is pointing to one and one is pointing

142
00:06:21,780 --> 00:06:22,590
to null.

143
00:06:22,590 --> 00:06:24,930
Now at this point again we move it right.

144
00:06:24,930 --> 00:06:28,620
So previous comes over here and current comes over here.

145
00:06:28,620 --> 00:06:31,380
Now current is now pointing to null.

146
00:06:31,380 --> 00:06:34,710
And at this point we can stop the function right.

147
00:06:34,710 --> 00:06:35,820
So we can stop it.

148
00:06:35,820 --> 00:06:42,120
So we can continue our loop through or continue the loop until current is not null, right?

149
00:06:42,120 --> 00:06:46,110
When current is null, we stop and we have our solution.

150
00:06:46,110 --> 00:06:48,000
So that's the way we are going to solve this.

151
00:06:48,000 --> 00:06:50,070
Now this is very easy.

152
00:06:50,070 --> 00:06:55,620
You can easily remember this if you just know that it's this pattern that we are following, right?

153
00:06:55,620 --> 00:06:57,720
Initially we have previous and current.

154
00:06:58,200 --> 00:07:01,410
Now inside the loop we will find next right.

155
00:07:01,410 --> 00:07:05,640
And then we will see where the connection and make current point to previous.

156
00:07:05,640 --> 00:07:07,770
Again we will move previous and current.

157
00:07:07,770 --> 00:07:09,960
We will find next inside the loop.

158
00:07:09,960 --> 00:07:13,740
And we will see where this connection and make current point to previous.

159
00:07:13,740 --> 00:07:16,470
So this is what we have been repeating again and again.

160
00:07:16,470 --> 00:07:18,900
Till current is not equal to null.

161
00:07:18,900 --> 00:07:24,510
When current is equal to null, we are done and we have our solution and we can just return previous,

162
00:07:24,510 --> 00:07:29,190
which is the head of the new singly linked list, which is reversed.

163
00:07:29,490 --> 00:07:30,810
Now that's the solution.

164
00:07:30,810 --> 00:07:35,430
Now let's quickly take a look at the complexity of this solution.

165
00:07:35,430 --> 00:07:38,970
Now the time complexity of this solution is going to be o of n.

166
00:07:38,970 --> 00:07:39,960
Why is that so?

167
00:07:39,960 --> 00:07:43,530
Because we are just traversing the linked list one time right.

168
00:07:43,530 --> 00:07:45,300
We're just traversing it one time.

169
00:07:45,300 --> 00:07:48,360
That's why the time complexity over here is O of n.

170
00:07:48,360 --> 00:07:50,520
Now what about the space complexity?

171
00:07:50,520 --> 00:07:52,950
The space complexity is O of one.

172
00:07:52,950 --> 00:07:53,640
Why is that?

173
00:07:53,640 --> 00:07:56,580
So we are not creating a new linked list, right?

174
00:07:56,580 --> 00:07:59,730
We are just changing the pointers.

175
00:07:59,730 --> 00:08:00,210
Right.

176
00:08:00,210 --> 00:08:04,020
We are just having reference pointers to existing objects in the memory.

177
00:08:04,020 --> 00:08:06,690
So those are these over here reference pointers.

178
00:08:06,690 --> 00:08:11,610
And then we are changing the direction in which particular nodes which are already there in memory are

179
00:08:11,610 --> 00:08:12,150
pointing.

180
00:08:12,150 --> 00:08:12,480
Right.

181
00:08:12,480 --> 00:08:14,700
So we are not using extra space.

182
00:08:14,700 --> 00:08:18,480
So that's why this runs in constant space or O of one.