1
00:00:00,970 --> 00:00:06,160
Hi everyone, I hope you have given it a try to code the solution, which we discussed in the previous

2
00:00:06,160 --> 00:00:09,040
video to reverse a singly linked list.

3
00:00:09,070 --> 00:00:11,950
Now over here, let's go ahead and code it together.

4
00:00:11,950 --> 00:00:16,660
Now I've written a class node and I have made a few nodes over here.

5
00:00:16,660 --> 00:00:17,800
So this is the head node.

6
00:00:17,800 --> 00:00:18,880
It has value one.

7
00:00:18,880 --> 00:00:21,490
And this points to a node with value two.

8
00:00:21,490 --> 00:00:23,620
And this points to a node with value three.

9
00:00:23,620 --> 00:00:25,960
And that points to a node with value four.

10
00:00:25,960 --> 00:00:27,880
Now we are going to write a function.

11
00:00:27,880 --> 00:00:32,110
Let's call this function reverse linked list.

12
00:00:34,590 --> 00:00:42,450
And this function is going to take as input a node which is the head node, and the output will be the

13
00:00:42,450 --> 00:00:45,630
new head node of the reversed singly linked list.

14
00:00:45,630 --> 00:00:47,520
So that's what we're trying to do over here.

15
00:00:47,520 --> 00:00:53,790
Now remember as we discussed in the previous video, the method that we are going to follow is we are

16
00:00:53,790 --> 00:00:55,980
going to have three pointers.

17
00:00:55,980 --> 00:01:00,600
We have one pointer called previous and then we have one pointer called current.

18
00:01:00,780 --> 00:01:01,050
All right.

19
00:01:01,050 --> 00:01:03,480
And we have a pointer called next.

20
00:01:03,480 --> 00:01:05,490
So we are just going to.

21
00:01:06,370 --> 00:01:08,680
Shift the direction in which current points.

22
00:01:08,710 --> 00:01:15,790
Now at this point, current is pointing to next at each uh, of these uh, instances like node one is

23
00:01:15,790 --> 00:01:18,820
the node with value, one is pointing to node with value two.

24
00:01:18,850 --> 00:01:19,480
Node.

25
00:01:19,480 --> 00:01:21,160
Let me just write that over here.

26
00:01:21,220 --> 00:01:25,840
So the node with value one is pointing to the node with value two.

27
00:01:25,840 --> 00:01:27,910
And that's pointing to the node with value three.

28
00:01:27,910 --> 00:01:30,370
And that's pointing to the node with value four.

29
00:01:30,370 --> 00:01:31,840
And that will point to null.

30
00:01:32,110 --> 00:01:34,240
Now we want to reverse this right.

31
00:01:34,240 --> 00:01:40,750
So the output that we want at the end is four which points to three which points to two which points

32
00:01:40,750 --> 00:01:41,410
to one.

33
00:01:41,410 --> 00:01:43,600
And that points to null.

34
00:01:43,600 --> 00:01:43,900
Right.

35
00:01:43,900 --> 00:01:46,390
So we're going to build this step by step.

36
00:01:46,390 --> 00:01:51,730
So initially we'll take this node which is the head node and will make it to point to null.

37
00:01:51,730 --> 00:01:56,140
And then we'll make know the node with value two to point to node one etc..

38
00:01:56,140 --> 00:01:56,350
Right.

39
00:01:56,350 --> 00:01:58,810
So that's the repetitive thing that we're going to do.

40
00:01:58,810 --> 00:02:04,810
And so to remember this just remember that what we are trying to do over here is we are going to change

41
00:02:04,810 --> 00:02:05,650
the direction right.

42
00:02:05,650 --> 00:02:08,500
Currently the current points to next.

43
00:02:08,500 --> 00:02:10,300
And we are going to change this direction.

44
00:02:10,300 --> 00:02:12,940
We'll make current point to previous.

45
00:02:12,940 --> 00:02:14,680
So that's what we are trying to do.

46
00:02:14,680 --> 00:02:15,100
All right.

47
00:02:15,100 --> 00:02:18,430
So if you have this in your mind then you can easily code this.

48
00:02:18,850 --> 00:02:20,140
So let's do it together.

49
00:02:20,140 --> 00:02:27,370
Now over here let me initially have a pointer previous and let it point to null.

50
00:02:27,370 --> 00:02:27,640
All right.

51
00:02:27,640 --> 00:02:29,860
So the value for prev is null.

52
00:02:29,860 --> 00:02:31,990
And let's have current.

53
00:02:32,650 --> 00:02:35,860
And this is set to the input node.

54
00:02:35,860 --> 00:02:37,390
Over here we are given the head.

55
00:02:37,390 --> 00:02:39,010
So we will set this to the head.

56
00:02:39,010 --> 00:02:41,920
And we need a next value right.

57
00:02:41,920 --> 00:02:44,230
Again this will come inside the loop right.

58
00:02:44,230 --> 00:02:45,250
So we'll have a loop.

59
00:02:45,250 --> 00:02:46,210
We'll have a while loop.

60
00:02:46,210 --> 00:02:49,450
And this will go on till there is a current node.

61
00:02:50,020 --> 00:02:54,640
And at each step we will just go to the next value of the current node.

62
00:02:54,760 --> 00:02:55,360
All right.

63
00:02:55,360 --> 00:02:57,910
Now again what will happen.

64
00:02:57,910 --> 00:03:03,040
So we'll have this loop will work when current node is pointing to one.

65
00:03:03,070 --> 00:03:05,260
It will work when it's pointing to two it will work.

66
00:03:05,260 --> 00:03:08,470
When it's pointing to three it will work when it's pointing to four.

67
00:03:08,470 --> 00:03:11,050
But when it's pointing to null, it will break.

68
00:03:11,050 --> 00:03:13,930
So that's what we are accomplishing through this loop.

69
00:03:13,930 --> 00:03:17,590
So we'll just have while current is true right.

70
00:03:18,390 --> 00:03:22,590
And inside this we will find the next value of current.

71
00:03:22,620 --> 00:03:24,450
Now why are we doing this?

72
00:03:24,450 --> 00:03:29,820
Because when we change the direction right over here, we are changing the direction current is pointing

73
00:03:29,850 --> 00:03:30,390
to next.

74
00:03:30,390 --> 00:03:34,650
And we said that our aim is to change the direction in which this points.

75
00:03:34,650 --> 00:03:40,770
Now when we change this, if we don't store the value of next somewhere, then we will lose the connection,

76
00:03:40,770 --> 00:03:41,070
right?

77
00:03:41,070 --> 00:03:43,140
So that's why we need to store next.

78
00:03:43,140 --> 00:03:45,720
And next is equal to current dot next.

79
00:03:45,870 --> 00:03:52,830
So once we have stored the next node then there is no no problem in changing the direction in which

80
00:03:52,830 --> 00:03:54,240
current is pointing.

81
00:03:54,240 --> 00:03:59,100
So we say current dot next is equal to previous.

82
00:03:59,610 --> 00:04:01,260
So we have changed the direction.

83
00:04:01,260 --> 00:04:03,510
So at this point we had one.

84
00:04:03,510 --> 00:04:06,180
So let's just write that over here.

85
00:04:06,180 --> 00:04:08,010
So we changed one.

86
00:04:08,010 --> 00:04:09,870
And now one is pointing to null.

87
00:04:09,870 --> 00:04:12,810
So we have one pointing to null right.

88
00:04:12,810 --> 00:04:14,550
And we have severed this connection.

89
00:04:14,550 --> 00:04:16,410
We don't have this connection anymore.

90
00:04:16,410 --> 00:04:20,100
But there is no problem because we have two stored in next.

91
00:04:20,100 --> 00:04:22,980
Now once we have done this what is it that we need to do?

92
00:04:22,980 --> 00:04:27,270
Remember we are going to shift the position of previous, current and next.

93
00:04:27,270 --> 00:04:30,030
So that's what we that is what we will be doing.

94
00:04:30,030 --> 00:04:30,600
Now.

95
00:04:30,600 --> 00:04:36,150
We just need to in this particular iteration, we just need to shift the position of previous and current

96
00:04:36,150 --> 00:04:36,870
pointers.

97
00:04:36,870 --> 00:04:41,670
And we will find the new next once we come back to this loop again.

98
00:04:41,670 --> 00:04:46,230
So at this point let's set previous to the current value.

99
00:04:46,230 --> 00:04:47,790
So previous is equal to current.

100
00:04:47,790 --> 00:04:50,640
So now we are over here right.

101
00:04:50,640 --> 00:04:52,710
So previous is pointing to one.

102
00:04:52,710 --> 00:04:55,800
And then we need current also to shift right.

103
00:04:55,800 --> 00:04:56,610
So current.

104
00:04:57,630 --> 00:05:00,000
Will point to the next value.

105
00:05:01,440 --> 00:05:03,120
So what have we done over here?

106
00:05:03,120 --> 00:05:06,750
We have made current to two and previous is pointing to one.

107
00:05:06,750 --> 00:05:10,530
So previous is pointing to one and the next of previous is null.

108
00:05:10,530 --> 00:05:10,980
All right.

109
00:05:10,980 --> 00:05:12,030
So we have done this.

110
00:05:12,030 --> 00:05:16,650
And once we have shifted the current pointer now current is over here.

111
00:05:16,650 --> 00:05:19,560
So what happens now current is two current is true.

112
00:05:19,560 --> 00:05:23,490
Again we come over here and we calculate next which is three.

113
00:05:23,490 --> 00:05:25,860
And we change the direction in which current points.

114
00:05:25,860 --> 00:05:27,600
So two dot next right.

115
00:05:27,600 --> 00:05:28,530
So that's equal to one.

116
00:05:28,530 --> 00:05:29,760
So we get two over here.

117
00:05:29,760 --> 00:05:31,140
And that points to two.

118
00:05:31,140 --> 00:05:33,120
And then we change this to previous.

119
00:05:33,120 --> 00:05:35,790
This becomes previous and current becomes three.

120
00:05:35,790 --> 00:05:36,330
Right.

121
00:05:36,330 --> 00:05:38,010
So we again do this.

122
00:05:38,010 --> 00:05:40,950
Now current is now equal to three.

123
00:05:40,950 --> 00:05:41,310
Right.

124
00:05:41,310 --> 00:05:42,870
And we put it over here.

125
00:05:44,030 --> 00:05:46,700
And current becomes four again.

126
00:05:46,700 --> 00:05:50,300
We put it over here and current dot next is null right.

127
00:05:50,300 --> 00:05:51,800
So at this point it's null.

128
00:05:51,800 --> 00:05:53,690
So we break out of this loop.

129
00:05:53,690 --> 00:05:57,650
And all we need to do is we need to return the new head.

130
00:05:58,010 --> 00:06:01,730
And what is the new head at this point the value of current is null right.

131
00:06:01,730 --> 00:06:05,210
We broke out of this while loop because the value of current is null.

132
00:06:05,210 --> 00:06:10,370
But you can see that previous is actually the new linked list which we are building.

133
00:06:10,370 --> 00:06:10,640
Right.

134
00:06:10,640 --> 00:06:15,320
So at this point this four is in previous the node with value four is previous.

135
00:06:15,320 --> 00:06:16,700
So that's the new head.

136
00:06:16,700 --> 00:06:18,560
So we just need to return that.

137
00:06:18,560 --> 00:06:21,410
And we have the solution to our question.

138
00:06:21,410 --> 00:06:21,830
All right.

139
00:06:21,830 --> 00:06:26,180
So let's try and run this and see whether this works.

140
00:06:26,180 --> 00:06:31,820
Now this is the initial uh singly list singly linked list which we have.

141
00:06:31,820 --> 00:06:35,000
So one points to two points to three points to four.

142
00:06:35,000 --> 00:06:37,790
Now let's see let's console log.

143
00:06:37,790 --> 00:06:41,780
What happens when we, uh, pass this singly linked list.

144
00:06:41,780 --> 00:06:45,680
The head of the singly linked list, which initially was there into our function.

145
00:06:45,680 --> 00:06:46,130
All right.

146
00:06:46,130 --> 00:06:49,550
So reverse linked list and we are passing head over here.

147
00:06:49,550 --> 00:06:52,790
Now let's see what it is that we are getting back.

148
00:06:54,020 --> 00:06:55,580
All right, so let me run this.

149
00:06:56,420 --> 00:06:58,850
Now, when we run this, we get this.

150
00:06:58,850 --> 00:07:00,440
So let's see what it is.

151
00:07:00,530 --> 00:07:04,400
So you can see that the value is four which is the last one.

152
00:07:04,400 --> 00:07:04,700
Right.

153
00:07:04,700 --> 00:07:10,670
So this is the value with four is the head now and that's pointing to the node with value three.

154
00:07:10,670 --> 00:07:13,280
And that is pointing to the node with value two.

155
00:07:13,280 --> 00:07:16,040
And that is pointing to the node with value one.

156
00:07:16,040 --> 00:07:18,140
And that in turn is pointing to null.

157
00:07:18,140 --> 00:07:22,130
So yes, we have successfully reversed the linked list right now.

158
00:07:22,130 --> 00:07:24,440
What if only had a single node.

159
00:07:24,440 --> 00:07:25,730
So let's try that.

160
00:07:25,730 --> 00:07:29,810
So let's say that we comment these lines.

161
00:07:29,810 --> 00:07:31,940
So we just have the head one right.

162
00:07:31,940 --> 00:07:34,310
So let's pass it and let's see what we get.

163
00:07:35,990 --> 00:07:36,290
All right.

164
00:07:36,290 --> 00:07:39,860
So again we get a node and we just return that node.

165
00:07:39,860 --> 00:07:41,690
So that's also working.

166
00:07:41,690 --> 00:07:44,600
Now if the input was null what would happen.

167
00:07:44,600 --> 00:07:45,830
Let's try that.

168
00:07:47,240 --> 00:07:49,220
In this case we are just returning null.

169
00:07:49,220 --> 00:07:52,040
So yes our code is working.

170
00:07:52,040 --> 00:07:54,680
It's passing all the test cases right.

171
00:07:54,680 --> 00:08:01,940
So we had a singly linked list in which the first node had a value one, the second had a value two.

172
00:08:01,940 --> 00:08:05,360
Then the third node had a value three and the fourth node had a value four.

173
00:08:05,360 --> 00:08:12,620
And when we pass this over here, we have seen that we got a reversed singly linked list.

174
00:08:12,620 --> 00:08:13,820
Right four three.

175
00:08:14,030 --> 00:08:16,490
And then we have two and we have one.

176
00:08:16,490 --> 00:08:17,720
And that points to null.

177
00:08:17,720 --> 00:08:19,310
So this is working all right.

178
00:08:19,310 --> 00:08:25,280
And you can see that in this function we are just traversing the singly linked list only one time.

179
00:08:25,280 --> 00:08:25,670
Right.

180
00:08:25,670 --> 00:08:27,140
We just traversing it once.

181
00:08:27,140 --> 00:08:30,530
So the time complexity of this solution is O of n.

182
00:08:30,530 --> 00:08:33,020
And the space complexity is O of one.

183
00:08:33,020 --> 00:08:35,720
Because we are not using any extra space, right.

184
00:08:35,720 --> 00:08:37,670
So it's running in constant space.

185
00:08:37,670 --> 00:08:43,700
Therefore the time complexity is O of n and the space complexity is O of one.

186
00:08:43,700 --> 00:08:49,910
Now let's take a relook at the code and let's take a simple test case and walk through it.