1
00:00:00,730 --> 00:00:03,160
Hi everyone, let's do this question.

2
00:00:03,160 --> 00:00:05,950
You are given the head of a linked list.

3
00:00:05,950 --> 00:00:11,050
Check if there is a cycle and if yes, return the node where the cycle begins.

4
00:00:11,050 --> 00:00:13,600
If there is no cycle, return null.

5
00:00:14,110 --> 00:00:16,090
There is a cycle in a linked list.

6
00:00:16,090 --> 00:00:22,300
If there is some node in the list that can be reached again by continuously following the next pointer,

7
00:00:22,300 --> 00:00:24,010
do not modify the linked list.

8
00:00:24,010 --> 00:00:25,270
So this is the question over here.

9
00:00:25,270 --> 00:00:28,510
Now for example, let's say this is the linked list which is given to us.

10
00:00:28,510 --> 00:00:30,820
So we will be given the head which is one.

11
00:00:30,820 --> 00:00:32,980
Now if you can just keep going next.

12
00:00:32,980 --> 00:00:35,320
So we go next we come over here again.

13
00:00:35,320 --> 00:00:36,190
We go to the next.

14
00:00:36,190 --> 00:00:37,660
So we are following the next pointer.

15
00:00:37,660 --> 00:00:43,150
We come over here and if we again follow the next pointer we are coming back to this node over here.

16
00:00:43,150 --> 00:00:45,670
So that means there is a cycle in the linked list.

17
00:00:45,670 --> 00:00:50,920
Now in this case we have to return the node where the cycle begins which is this node over here.

18
00:00:50,920 --> 00:00:52,480
That is this question over here.

19
00:00:52,480 --> 00:00:55,330
Now let's go ahead and write a few test cases.

20
00:00:55,330 --> 00:00:58,540
Now let's say the linked list which is given to us is this one over here.

21
00:00:58,540 --> 00:01:02,980
Now in this case you can see there is a cycle over here and it's starting over here.

22
00:01:02,980 --> 00:01:05,770
So we have to return the node three over here.

23
00:01:05,770 --> 00:01:10,330
Now if the linked list looks something like this that is one going to two going to three.

24
00:01:10,330 --> 00:01:12,040
And then that's pointing to null.

25
00:01:12,040 --> 00:01:13,870
So there is no cycle.

26
00:01:13,870 --> 00:01:16,570
And in that case we have to just return null.

27
00:01:16,900 --> 00:01:18,700
And let's write a few more test cases.

28
00:01:18,700 --> 00:01:21,820
Let's say the linked list has just one node.

29
00:01:21,820 --> 00:01:22,690
Now over here.

30
00:01:22,690 --> 00:01:26,020
Also we have to return null because clearly there is no cycle.

31
00:01:26,020 --> 00:01:30,340
And if the linked list is just null, that is there is no node even at the head.

32
00:01:30,340 --> 00:01:34,330
Then also we have to return null because clearly there is no cycle.

33
00:01:34,330 --> 00:01:39,460
Now in the next video, let's try to think how we can solve this in an efficient manner.