1
00:00:00,460 --> 00:00:01,450
Welcome back.

2
00:00:01,450 --> 00:00:06,640
Let's now go ahead and code the solution, which we discussed in the previous video, to check if there

3
00:00:06,640 --> 00:00:09,790
is a cycle in the linked list which is given to us.

4
00:00:09,790 --> 00:00:15,010
Now over here I have written the class node and using this I've created these nodes one, two, three,

5
00:00:15,010 --> 00:00:16,330
four, five and six.

6
00:00:16,330 --> 00:00:22,630
And then I've connected 1 to 2, 2 to 3, 3 to 4, 4 to 5 and 5 to 6.

7
00:00:22,630 --> 00:00:26,410
And then I've made a loop over here so that we can test the code once we've written it.

8
00:00:26,410 --> 00:00:29,080
So six is going to be connected to two.

9
00:00:29,080 --> 00:00:29,470
All right.

10
00:00:29,470 --> 00:00:36,370
So when we run the code and if we detect it correctly that there is a cycle, then we have to detect

11
00:00:36,370 --> 00:00:41,800
that the cycle begins at two because six, which is the last node over here is again connected to two.

12
00:00:41,830 --> 00:00:42,310
All right.

13
00:00:42,310 --> 00:00:44,800
And then we are just setting head to be equal to one.

14
00:00:44,800 --> 00:00:49,870
So once we write the function as described in the question, we will be passing the head of the linked

15
00:00:49,870 --> 00:00:51,070
list to the function.

16
00:00:51,070 --> 00:00:52,870
So let's go ahead and write the function.

17
00:00:52,870 --> 00:00:54,160
So let's write it over here.

18
00:00:55,700 --> 00:00:58,220
Now let's call this function check loop.

19
00:01:00,310 --> 00:01:04,000
And this function is going to take in the head of the linked list.

20
00:01:06,360 --> 00:01:06,870
All right.

21
00:01:06,870 --> 00:01:10,650
Now, once we are inside the function, let's just check if the head is null.

22
00:01:10,650 --> 00:01:16,650
So if not head, then we can just return null, which means that there is no loop, right?

23
00:01:16,650 --> 00:01:19,200
So if the head itself is null, there is no loop.

24
00:01:19,200 --> 00:01:21,060
And if it's just a single node.

25
00:01:21,060 --> 00:01:21,960
So let's just check that.

26
00:01:21,960 --> 00:01:23,940
If not head dot next.

27
00:01:24,900 --> 00:01:27,900
That is, if there is just one node in the linked list.

28
00:01:27,900 --> 00:01:28,650
In that case.

29
00:01:28,650 --> 00:01:32,910
Also, we know that there is no loop and we can just return null.

30
00:01:32,940 --> 00:01:33,480
All right.

31
00:01:33,510 --> 00:01:35,880
Now if this is not the case let's proceed.

32
00:01:35,880 --> 00:01:39,810
So let's have here and here is going to point at the head.

33
00:01:39,810 --> 00:01:42,030
And we will have the tortoise also.

34
00:01:43,110 --> 00:01:46,050
And the tortoise is also going to point at the head.

35
00:01:46,080 --> 00:01:53,370
Now we are going to keep looping as long as the hair is not at null, and as long as the hair can move

36
00:01:53,370 --> 00:01:54,450
two pointers, right.

37
00:01:54,450 --> 00:01:55,800
So let's do that over here.

38
00:01:56,770 --> 00:02:00,940
While hair and hair dot next.

39
00:02:03,770 --> 00:02:04,100
Right?

40
00:02:04,100 --> 00:02:07,010
So as long as this is true, we will keep looping.

41
00:02:07,010 --> 00:02:14,540
So if there was no cycle in the given linked list, then this would keep looping as long as hair dot

42
00:02:14,540 --> 00:02:14,990
next right.

43
00:02:14,990 --> 00:02:20,300
Hair dot next would be uh becoming null when hair is at the tail, right?

44
00:02:20,300 --> 00:02:25,430
So if hair is at the tail then hair dot next will not be, uh, will not be a valid node.

45
00:02:25,430 --> 00:02:26,750
And it is it's going to be null.

46
00:02:26,750 --> 00:02:28,550
So we're going to stop at that point.

47
00:02:28,550 --> 00:02:28,940
All right.

48
00:02:28,940 --> 00:02:30,110
So that's fine.

49
00:02:30,110 --> 00:02:34,550
We can because the reason is that we want the hair to jump two nodes at a time.

50
00:02:34,550 --> 00:02:36,620
And if hair dot next is null.

51
00:02:36,620 --> 00:02:39,920
And if we again call dot next on that it will throw an error.

52
00:02:39,920 --> 00:02:41,210
So we want to avoid that.

53
00:02:41,210 --> 00:02:44,930
So as long as this is not the case we keep moving forward.

54
00:02:44,930 --> 00:02:47,180
So hair is going to move two nodes at a time.

55
00:02:47,180 --> 00:02:49,160
So we can say hair is equal to hair.

56
00:02:49,160 --> 00:02:51,440
Dot next dot next.

57
00:02:51,860 --> 00:02:54,290
And the tortoise is going to move one node at a time.

58
00:02:54,290 --> 00:02:57,710
So tortoise is equal to tortoise dot next.

59
00:02:58,400 --> 00:02:58,910
All right.

60
00:02:58,940 --> 00:03:01,520
Now once again inside this loop.

61
00:03:01,520 --> 00:03:05,720
Also we will keep checking if the hair is equal to tortoise right.

62
00:03:05,720 --> 00:03:09,770
Because if there is a loop this will keep going on without any end.

63
00:03:09,770 --> 00:03:11,960
Because if there is a loop right there's a cycle.

64
00:03:11,960 --> 00:03:13,820
So it's never going to be false.

65
00:03:13,940 --> 00:03:17,150
So hair and hair dot next will never be false if there is a loop.

66
00:03:17,150 --> 00:03:22,850
So if there is a loop, the way we come out of this while loop is if hair is equal to tortoise.

67
00:03:22,850 --> 00:03:24,470
So that means they have met.

68
00:03:24,470 --> 00:03:27,500
And in that case we will just break out of the while loop.

69
00:03:28,480 --> 00:03:28,900
All right.

70
00:03:28,930 --> 00:03:34,840
Now, once we are out of the while loop, let's check whether they have whether the reason for breaking

71
00:03:34,840 --> 00:03:40,240
out of the loop was that they have met, or is it another reason, like for example, they have reached

72
00:03:40,240 --> 00:03:40,870
the tail.

73
00:03:40,870 --> 00:03:42,130
So let's check that over here.

74
00:03:42,130 --> 00:03:43,120
So if.

75
00:03:44,180 --> 00:03:46,820
Here not equal to tortoise.

76
00:03:47,060 --> 00:03:48,890
That means they have not met.

77
00:03:48,890 --> 00:03:50,690
And we came out of the while loop.

78
00:03:50,720 --> 00:03:53,360
That means that there is no loop, right?

79
00:03:53,360 --> 00:03:54,140
So there is no loop.

80
00:03:54,140 --> 00:03:56,570
So we can just return null in that case.

81
00:03:56,810 --> 00:04:00,080
Now, if that is not the case, it means that they have met.

82
00:04:00,080 --> 00:04:02,690
And that's the reason that we came out of the while loop.

83
00:04:02,690 --> 00:04:07,790
So now let's try to find where the loop or the cycle begins.

84
00:04:08,720 --> 00:04:10,340
Let's try to find this now.

85
00:04:10,340 --> 00:04:12,200
For this we will need a pointer.

86
00:04:12,200 --> 00:04:13,970
Let's call it pointer itself.

87
00:04:13,970 --> 00:04:15,680
And this is going to point at the head.

88
00:04:15,710 --> 00:04:22,160
Now we will move the head and the tortoise one step at a time as long as they don't meet.

89
00:04:22,160 --> 00:04:26,600
So while pointer not equal to tortoise.

90
00:04:27,840 --> 00:04:30,450
We will keep moving them one step at a time.

91
00:04:30,450 --> 00:04:33,480
So pointer is equal to pointer dot.

92
00:04:33,480 --> 00:04:34,230
Next.

93
00:04:35,660 --> 00:04:37,790
And tortoise is equal to.

94
00:04:38,710 --> 00:04:40,600
Tortoise dot next.

95
00:04:40,960 --> 00:04:45,100
So they are moving one node at a time and when they meet we come out.

96
00:04:45,100 --> 00:04:50,320
And at that point we have identified the node where the cycle begins.

97
00:04:50,320 --> 00:04:53,380
So we can just return the tortoise or the pointer.

98
00:04:53,380 --> 00:04:56,560
So let's just return the tortoise over here and that's it.

99
00:04:56,560 --> 00:05:01,570
So this is the solution to the code the solution to the question that we have seen.

100
00:05:01,570 --> 00:05:07,270
So over here we have seen we are able to find whether there is a cycle or not in constant space.

101
00:05:07,270 --> 00:05:13,210
Now that's that's as, as compared to the brute force solution where we would have need to have a hash

102
00:05:13,210 --> 00:05:17,080
table or a set, etc., which will take O of n space.

103
00:05:17,080 --> 00:05:20,590
Now let's take um, let's just call this function, let's walk.

104
00:05:20,620 --> 00:05:24,070
Uh, let's call this function using what we have set up over here for testing.

105
00:05:24,070 --> 00:05:26,710
So we will pass in the head and let's see what's happening.

106
00:05:26,710 --> 00:05:28,420
So we will say check loop.

107
00:05:28,420 --> 00:05:30,010
And we pass in the head.

108
00:05:30,610 --> 00:05:35,860
And our expectation is that we should get back two which is the beginning of the loop.

109
00:05:36,620 --> 00:05:38,870
So let's see what we are getting when we run the code.

110
00:05:38,870 --> 00:05:40,610
Yes, we are getting two over here.

111
00:05:40,610 --> 00:05:42,170
So that's this node right.

112
00:05:42,170 --> 00:05:43,670
That's this node with value two.

113
00:05:43,670 --> 00:05:44,030
Right.

114
00:05:44,030 --> 00:05:45,620
So this is pointing to three.

115
00:05:45,620 --> 00:05:47,480
And again yes that's a loop we know.

116
00:05:47,480 --> 00:05:48,680
So yes that's correct.

117
00:05:48,710 --> 00:05:50,300
Now what if we change this.

118
00:05:50,300 --> 00:05:51,500
What if we change this.

119
00:05:51,500 --> 00:05:54,110
And we say six dot next is equal to three.

120
00:05:54,500 --> 00:05:58,190
In this case the cycle begins at node three.

121
00:05:58,190 --> 00:05:59,840
And we should get back that node.

122
00:05:59,840 --> 00:06:01,220
So yes we are getting that.

123
00:06:01,220 --> 00:06:03,800
And what if we just comment this out.

124
00:06:03,800 --> 00:06:08,990
That is if we are removing the loop in this case we should see that there is no loop and we should just

125
00:06:08,990 --> 00:06:09,860
get null.

126
00:06:10,520 --> 00:06:14,450
Yes that's true, we are getting null and let's say it's just null over here.

127
00:06:14,450 --> 00:06:19,940
So if the input is itself just null in that case also we will get null which is true.

128
00:06:19,940 --> 00:06:21,560
And let's say we have one more node.

129
00:06:21,560 --> 00:06:24,350
So let's create one more node over here just for testing.

130
00:06:24,350 --> 00:06:30,800
So let's say const seven is equal to new node and it has the value seven.

131
00:06:30,800 --> 00:06:33,380
And let's say we are not connecting anything to it.

132
00:06:33,380 --> 00:06:36,410
So that's just a linked list with one node.

133
00:06:36,410 --> 00:06:40,010
And let's say we are passing this node over here to our check loop.

134
00:06:40,340 --> 00:06:40,640
Right.

135
00:06:40,640 --> 00:06:44,840
So in this case we also get null because there is just one node and there is no loop.

136
00:06:44,840 --> 00:06:46,700
So yes our code is working.

137
00:06:46,700 --> 00:06:52,070
Now let's just take this initial sample which we had where we had these six nodes.

138
00:06:52,070 --> 00:06:54,530
And let's say six dot next is equal to three.

139
00:06:54,530 --> 00:06:57,950
And let's walk through the code and try to understand what's happening over here.

140
00:06:57,950 --> 00:06:59,840
So for this let's grab a pen.

141
00:07:00,440 --> 00:07:00,920
All right.

142
00:07:00,920 --> 00:07:05,030
So let's go ahead and draw this out so that we can visualize this in a better manner.

143
00:07:05,030 --> 00:07:10,880
So we have one which is pointing to two which is pointing to three which is pointing to four which is

144
00:07:10,880 --> 00:07:11,990
pointing to five.

145
00:07:11,990 --> 00:07:17,480
And then that's pointing to six, and six is pointing to again, uh, let's just check that over here.

146
00:07:17,480 --> 00:07:19,790
Six is pointing to three.

147
00:07:19,790 --> 00:07:20,030
Right.

148
00:07:20,030 --> 00:07:21,290
So six is pointing to three.

149
00:07:21,290 --> 00:07:22,370
So let's draw that.

150
00:07:24,030 --> 00:07:26,610
So this is how the linked list looks like.

151
00:07:26,610 --> 00:07:29,880
And we are passing the head to the check loop function.

152
00:07:29,880 --> 00:07:33,000
So again let's just change this over here we are passing the head right.

153
00:07:33,450 --> 00:07:36,120
So that was the initial example which you're trying to walk through.

154
00:07:36,120 --> 00:07:40,350
Now let's try to look at what is happening in the function that we have written.

155
00:07:40,350 --> 00:07:42,600
So we are inside the check loop function.

156
00:07:43,430 --> 00:07:47,810
And we see that the head is not null and head dot next is also not null.

157
00:07:47,810 --> 00:07:49,070
So we come over here.

158
00:07:49,070 --> 00:07:54,050
Now here is pointing at the head and the tortoise is also pointing at the head.

159
00:07:54,050 --> 00:07:56,240
Now we are going to have this while loop.

160
00:07:56,240 --> 00:07:57,440
So let's just walk through it.

161
00:07:57,440 --> 00:07:58,430
So here is truthy.

162
00:07:58,430 --> 00:07:59,870
And here dot next is truthy.

163
00:07:59,870 --> 00:08:01,580
So we are inside the while loop.

164
00:08:01,580 --> 00:08:03,380
And here is moving two steps.

165
00:08:03,380 --> 00:08:04,670
So here comes over here.

166
00:08:05,180 --> 00:08:07,220
And the tortoise moves one step.

167
00:08:07,220 --> 00:08:08,510
So tortoise is over here.

168
00:08:09,480 --> 00:08:11,280
Now is are these two equal?

169
00:08:11,310 --> 00:08:12,390
No, they are not equal.

170
00:08:12,390 --> 00:08:13,830
So again is here truthy.

171
00:08:13,830 --> 00:08:14,280
Yes.

172
00:08:14,280 --> 00:08:15,750
And is here dot next.

173
00:08:15,750 --> 00:08:16,140
Truthy.

174
00:08:16,140 --> 00:08:16,560
Yes.

175
00:08:16,560 --> 00:08:18,390
So we come again inside the while loop.

176
00:08:18,390 --> 00:08:20,250
And the hair is moving two steps.

177
00:08:20,250 --> 00:08:21,450
So it comes over here.

178
00:08:21,900 --> 00:08:27,750
And the tortoise moves one step and it comes over here again we see that the condition is true.

179
00:08:27,930 --> 00:08:29,550
So we are inside the while loop.

180
00:08:29,550 --> 00:08:30,810
The hair moves two steps.

181
00:08:30,810 --> 00:08:32,100
So it comes over here.

182
00:08:32,100 --> 00:08:33,420
And then it comes over here.

183
00:08:33,420 --> 00:08:39,660
And when the hair comes over here the tortoise moves one step and comes over here again.

184
00:08:39,660 --> 00:08:41,880
The hare and the tortoise have not met.

185
00:08:41,880 --> 00:08:43,470
So we are again moving.

186
00:08:43,470 --> 00:08:44,670
So we come inside the while loop.

187
00:08:44,670 --> 00:08:45,090
Again.

188
00:08:45,090 --> 00:08:48,630
The tortoise is going to move one step and the hair is moving two steps.

189
00:08:48,630 --> 00:08:54,120
So the hair comes over here and the tortoise also when it moves, one step comes over here and you can

190
00:08:54,120 --> 00:08:55,140
see that they have met.

191
00:08:55,140 --> 00:08:55,500
Right.

192
00:08:55,500 --> 00:08:58,200
So the hare and the tortoise is at this point have met.

193
00:08:58,200 --> 00:09:00,480
And both of them are at node five.

194
00:09:00,480 --> 00:09:02,970
So we are going to have one pointer.

195
00:09:02,970 --> 00:09:04,950
So this is going to be pointer.

196
00:09:05,190 --> 00:09:06,900
And then we have the tortoise right.

197
00:09:06,900 --> 00:09:08,310
That's what we are doing over here.

198
00:09:08,310 --> 00:09:12,360
We see that the hare uh is the hare not equal to the tortoise.

199
00:09:12,360 --> 00:09:13,410
No that's not the case.

200
00:09:13,410 --> 00:09:15,330
They have met so we don't return null.

201
00:09:15,330 --> 00:09:18,960
So we come over here and we have a pointer which is pointing to the head.

202
00:09:18,960 --> 00:09:24,510
And then while the pointer is not equal to the tortoise, we are going to move them one step at a time.

203
00:09:24,510 --> 00:09:26,400
So the pointer comes over here.

204
00:09:27,770 --> 00:09:29,660
And the tortoise comes over here.

205
00:09:30,720 --> 00:09:32,700
And again they are not equal.

206
00:09:32,700 --> 00:09:33,870
So again they move.

207
00:09:33,870 --> 00:09:38,010
The pointer comes over here and the tortoise also comes over here.

208
00:09:38,010 --> 00:09:41,550
And at this point they are both pointing to node three.

209
00:09:41,550 --> 00:09:46,110
And therefore we come out and we are going to just return the tortoise which is node three.

210
00:09:46,110 --> 00:09:48,150
And that is the beginning of the cycle.

211
00:09:48,150 --> 00:09:49,920
So this is how this function works.

212
00:09:49,920 --> 00:09:54,180
Now let's take a quick look at the space and time complexity of this solution.

213
00:09:54,180 --> 00:09:56,130
Now what about the time complexity.

214
00:09:56,130 --> 00:10:02,430
The time complexity is going to be O of N because over here in the while loop you can see we will keep

215
00:10:02,430 --> 00:10:09,300
looping as long as either the hair should reach the tail right, the hair should reach the tail, or

216
00:10:09,300 --> 00:10:11,520
the hair should be equal to the tortoise.

217
00:10:11,520 --> 00:10:14,760
So if the hair reaches the tail, that's n operations.

218
00:10:14,760 --> 00:10:19,890
And if that is not the case, they will meet before the tortoise does n moves, right.

219
00:10:19,890 --> 00:10:21,480
So we have seen that in the previous video.

220
00:10:21,480 --> 00:10:25,050
So over here we are going to do maximum n operations.

221
00:10:25,050 --> 00:10:30,690
And then once that is done over here we are going to do less than N operations to get the pointer and

222
00:10:30,690 --> 00:10:31,830
the tortoise to meet.

223
00:10:31,830 --> 00:10:35,220
So that's why the time complexity of this solution is O of n.

224
00:10:35,220 --> 00:10:40,740
And the space complexity of the solution is just O of one, because we are not using any auxiliary space.

225
00:10:40,740 --> 00:10:43,410
So this solution runs in constant space.