1 00:00:00,500 --> 00:00:01,490 Welcome back. 2 00:00:01,490 --> 00:00:07,400 In this video, let's try to understand why this distance over here is going to be equal to the distance 3 00:00:07,400 --> 00:00:07,820 over here. 4 00:00:07,820 --> 00:00:08,000 Right. 5 00:00:08,000 --> 00:00:12,440 So we have to move one two nodes from the head to reach this node. 6 00:00:12,440 --> 00:00:17,690 And then from here also if we move one and then the second node we are again going to reach over here. 7 00:00:17,690 --> 00:00:21,230 So we are going to try to understand why these two distances are the same. 8 00:00:21,230 --> 00:00:22,760 So that's this proof over here. 9 00:00:22,760 --> 00:00:24,590 Now I've just set it up over here. 10 00:00:24,590 --> 00:00:28,100 Let's say the nodes which are not part of the cycle is equal to x. 11 00:00:28,100 --> 00:00:30,320 And then let's say this is the meeting point. 12 00:00:30,320 --> 00:00:35,060 So the distance from the first node of the cycle to the meeting point is equal to m. 13 00:00:35,060 --> 00:00:38,420 And then let's say the length of the cycle is equal to c. 14 00:00:38,450 --> 00:00:41,690 For example in this case that's 3456 and seven. 15 00:00:41,690 --> 00:00:43,100 So the cycle length is seven. 16 00:00:43,100 --> 00:00:45,230 And over here this is 3456. 17 00:00:45,230 --> 00:00:47,900 So m is equal to six and x is equal to two. 18 00:00:47,900 --> 00:00:48,680 For example. 19 00:00:48,680 --> 00:00:55,400 Now if the meeting is going to happen over here then the hare and the tortoise have to reach over here. 20 00:00:55,400 --> 00:01:01,340 Now when the hare reaches over here let's say it has done n cycles over here and then finally reached 21 00:01:01,340 --> 00:01:02,000 back over here. 22 00:01:02,000 --> 00:01:08,330 So we can say the hare has moved x plus n into C, which is n cycles plus m, right. 23 00:01:08,330 --> 00:01:13,760 And in the same time we can say that the tortoise has done x plus m nodes. 24 00:01:13,760 --> 00:01:15,650 It has travelled x plus m nodes. 25 00:01:15,680 --> 00:01:16,130 All right. 26 00:01:16,130 --> 00:01:21,800 So this is the distance or the number of nodes that the hare and the tortoise has travelled. 27 00:01:22,280 --> 00:01:26,990 Now we know that the hare is traveling at twice the speed of the tortoise. 28 00:01:26,990 --> 00:01:31,400 So we can see that n h will be equal to two times n into t. 29 00:01:31,400 --> 00:01:36,530 That is, the number of nodes that the hare travels is going to be twice the number of nodes that the 30 00:01:36,530 --> 00:01:37,970 tortoise is going to travel. 31 00:01:37,970 --> 00:01:41,240 So let's substitute these two into this equation over here. 32 00:01:41,240 --> 00:01:47,330 So we get x plus NC plus m is equal to two times x plus m. 33 00:01:47,330 --> 00:01:49,430 And that's equal to two x plus two m. 34 00:01:49,430 --> 00:01:51,290 So let's try to simplify this. 35 00:01:51,290 --> 00:01:55,850 Now this simplifies to NC is equal to x plus m right. 36 00:01:55,850 --> 00:01:58,190 So NC is equal to x plus m. 37 00:01:58,190 --> 00:02:05,360 Now if NC is equal to x plus m then we can say that x is equal to NC minus m. 38 00:02:05,360 --> 00:02:07,610 So I've just taken m to the left hand side. 39 00:02:07,610 --> 00:02:10,340 So x is equal to NC minus m. 40 00:02:10,340 --> 00:02:12,410 Now over here we have x nodes. 41 00:02:12,410 --> 00:02:17,150 So to reach over here the pointer which is over here has to do one two. 42 00:02:17,180 --> 00:02:19,010 It has to do two two moves right. 43 00:02:19,010 --> 00:02:20,570 It has to move two times. 44 00:02:20,570 --> 00:02:24,830 So if this pointer is traveling x nodes. 45 00:02:25,740 --> 00:02:32,940 Then we can see that if the pointer p two moves NC minus m nodes, right? 46 00:02:32,940 --> 00:02:36,690 So I know that the number of times they are moving is the same. 47 00:02:36,690 --> 00:02:36,960 Right? 48 00:02:36,960 --> 00:02:42,390 So when P is moving over here, this node also is moving the same number of times because we are moving 49 00:02:42,390 --> 00:02:43,650 them simultaneously. 50 00:02:43,650 --> 00:02:50,340 The only thing that we are trying to prove is that when p is moving x no x times it's going to reach 51 00:02:50,340 --> 00:02:50,790 over here. 52 00:02:50,790 --> 00:02:52,740 And this one also is going to reach over here. 53 00:02:52,740 --> 00:02:59,580 So when p is traveling x nodes because x is equal to NC minus m, we can say that p two which is this 54 00:02:59,580 --> 00:03:02,580 pointer over here travels NC minus m nodes. 55 00:03:02,580 --> 00:03:08,670 That is true that we know because they are traveling together now NC minus m, I can rewrite it as n 56 00:03:08,670 --> 00:03:10,830 minus one c plus c minus m. 57 00:03:10,830 --> 00:03:13,290 So I'm just taking one c out of NC. 58 00:03:13,290 --> 00:03:16,110 So this is n minus one c plus c right. 59 00:03:16,110 --> 00:03:17,280 That is equal to NC. 60 00:03:17,280 --> 00:03:22,080 So I'm just splitting it up in this manner now n minus one into C. 61 00:03:22,080 --> 00:03:22,500 Right. 62 00:03:22,500 --> 00:03:28,710 So if the pointer which is over here is doing n minus one cycles it will again reach back over here 63 00:03:28,710 --> 00:03:29,760 wherever it started. 64 00:03:29,760 --> 00:03:29,910 Right. 65 00:03:29,910 --> 00:03:34,560 So it will be back at its initial position when it's doing some number of cycles. 66 00:03:34,560 --> 00:03:39,270 And then the remaining distance that this travels is equal to c minus m. 67 00:03:39,750 --> 00:03:43,140 And we know that c is the distance the length of the cycle. 68 00:03:43,140 --> 00:03:45,150 So c minus m right. 69 00:03:45,150 --> 00:03:45,780 This is c. 70 00:03:45,780 --> 00:03:51,360 And this over here is m is actually if you subtract c minus m that's the distance between this node 71 00:03:51,360 --> 00:03:53,160 and the beginning node. 72 00:03:53,160 --> 00:04:00,600 So that is why we can say that when the head pointer is moving x nodes then the pointer which is at 73 00:04:00,600 --> 00:04:07,410 the meeting point also will move such number of nodes such that both of them is going to be at the node 74 00:04:07,410 --> 00:04:08,730 where the cycle begins. 75 00:04:08,730 --> 00:04:13,860 So that is why we can use this method to find the beginning of the cycle. 76 00:04:13,860 --> 00:04:16,200 That is, the node where the cycle begins.