1 00:00:01,040 --> 00:00:06,860 Hi everyone, we have successfully coded the solution for this question which we have discussed. 2 00:00:06,860 --> 00:00:12,590 Now let's take a sample input and walk through the code that we have written, especially through this 3 00:00:12,590 --> 00:00:13,490 function over here. 4 00:00:13,490 --> 00:00:18,230 Now this code over here, over here we have class node and then this part over here. 5 00:00:18,230 --> 00:00:21,290 This is written so that we can test the function that we have written. 6 00:00:21,290 --> 00:00:21,590 Right. 7 00:00:21,590 --> 00:00:26,600 So when this code executes we will get a singly linked list right. 8 00:00:26,600 --> 00:00:27,440 Singly linked list. 9 00:00:27,440 --> 00:00:28,910 And this is how it looks. 10 00:00:28,910 --> 00:00:30,710 We have one which points to two. 11 00:00:30,710 --> 00:00:34,280 Which points to two which points to a node with value three. 12 00:00:34,280 --> 00:00:39,170 And over here the last two nodes have a value of a right a character a. 13 00:00:39,200 --> 00:00:44,690 So we have just made five nodes and then we have connected them using Dot next operation right over 14 00:00:44,690 --> 00:00:44,990 here. 15 00:00:44,990 --> 00:00:46,730 So this is the singly linked list. 16 00:00:46,730 --> 00:00:50,960 And the head of this singly linked list is this node over here. 17 00:00:50,960 --> 00:00:53,960 And that's what we are passing to this function over here. 18 00:00:53,960 --> 00:00:54,380 All right. 19 00:00:54,380 --> 00:00:57,470 So again here we are calling the function remove dupes. 20 00:00:57,470 --> 00:00:58,850 And then we are passing the head. 21 00:00:58,970 --> 00:00:59,600 All right. 22 00:00:59,600 --> 00:01:04,520 So once we are inside this function we set the curve value to the head. 23 00:01:04,520 --> 00:01:06,860 So curve will point to the head at this point. 24 00:01:06,860 --> 00:01:10,880 Now car is coming truthy because it has a node right. 25 00:01:10,880 --> 00:01:12,050 So we are in the while loop. 26 00:01:12,050 --> 00:01:17,900 We go inside it and this will keep repeating till current comes to null at that point. 27 00:01:17,900 --> 00:01:24,050 While car this part, when it is null, it will become false and we come out of the while loop and we 28 00:01:24,050 --> 00:01:25,040 return the head. 29 00:01:25,040 --> 00:01:27,560 So that's what's happening inside this function. 30 00:01:27,560 --> 00:01:32,840 Now initially over here we can see we are setting next distinct val as car dot next. 31 00:01:32,840 --> 00:01:35,900 So at this point this is next distinct val. 32 00:01:35,900 --> 00:01:38,570 So I'm just writing next over here to keep it short. 33 00:01:38,570 --> 00:01:38,960 All right. 34 00:01:38,960 --> 00:01:44,930 So using this line of code we are pointing next distinct val to the next node which is this one over 35 00:01:44,930 --> 00:01:45,410 here. 36 00:01:45,410 --> 00:01:52,820 Now over here in the while loop inside we are checking whether these two are of the same value or not. 37 00:01:52,820 --> 00:01:53,180 Right. 38 00:01:53,180 --> 00:01:59,600 So we are checking that over here car dot val equal to equal to equal to next distinct dot val right 39 00:01:59,600 --> 00:02:01,370 next next distinct val dot val. 40 00:02:01,370 --> 00:02:04,010 So over here we can see that they are not equal. 41 00:02:04,010 --> 00:02:05,810 So we don't go inside the loop. 42 00:02:05,810 --> 00:02:10,550 And over here we do car next is equal to next distinct val which is already two. 43 00:02:10,580 --> 00:02:11,780 In true in this case. 44 00:02:11,780 --> 00:02:13,400 So nothing is changing. 45 00:02:13,400 --> 00:02:19,040 So this is actually required only when the case is where we had some nodes to delete. 46 00:02:19,040 --> 00:02:19,250 Right. 47 00:02:19,250 --> 00:02:21,740 But again over here we don't have anything to delete. 48 00:02:21,740 --> 00:02:24,230 But so this is the already existing situation. 49 00:02:24,230 --> 00:02:25,490 So nothing changes. 50 00:02:25,490 --> 00:02:27,920 And we set car is equal to next distinct Val. 51 00:02:27,920 --> 00:02:30,050 So car comes to this part right. 52 00:02:30,050 --> 00:02:32,990 So over here car points to the second node. 53 00:02:32,990 --> 00:02:35,030 And car is still true. 54 00:02:35,030 --> 00:02:35,360 Right. 55 00:02:35,360 --> 00:02:36,560 So it's it's truthy. 56 00:02:36,560 --> 00:02:41,750 So again the while loop is executed and we set next to the next node. 57 00:02:41,750 --> 00:02:42,110 Right. 58 00:02:42,110 --> 00:02:43,970 And we are going to compare these two. 59 00:02:44,000 --> 00:02:46,370 Now in this while loop we are going to compare them. 60 00:02:46,370 --> 00:02:48,530 And they are having the same value. 61 00:02:48,530 --> 00:02:50,030 And next distinct val. 62 00:02:50,030 --> 00:02:51,740 This one over here is not equal to null. 63 00:02:51,740 --> 00:02:53,060 So we come inside right. 64 00:02:53,060 --> 00:02:55,460 So we come inside and we do. 65 00:02:55,460 --> 00:02:58,610 Next distinct val is equal to next distinct val dot next. 66 00:02:58,610 --> 00:03:00,860 So we move this one step ahead right. 67 00:03:00,860 --> 00:03:06,470 So we come over here again in the while loop we check whether these two have the same value right. 68 00:03:06,470 --> 00:03:07,850 So this will not be true. 69 00:03:07,850 --> 00:03:09,650 Therefore we come over here right. 70 00:03:09,650 --> 00:03:12,800 Therefore we come over here and we say car dot next. 71 00:03:13,250 --> 00:03:17,180 That is the next from this node is equal to next distinct val. 72 00:03:17,180 --> 00:03:20,810 So we make this node point to this one over here. 73 00:03:21,590 --> 00:03:21,980 All right. 74 00:03:21,980 --> 00:03:24,680 So that effectively deletes this node. 75 00:03:24,680 --> 00:03:24,980 Right. 76 00:03:24,980 --> 00:03:27,590 So two is now pointing to this node over here. 77 00:03:27,590 --> 00:03:29,810 So we could keep doing that again and again. 78 00:03:29,810 --> 00:03:30,200 Right. 79 00:03:30,200 --> 00:03:33,740 So in this case also we will make this node point to null. 80 00:03:34,220 --> 00:03:40,850 And finally when Kerr is equal to null this while loop breaks and we come out and we return the head 81 00:03:40,850 --> 00:03:41,090 right. 82 00:03:41,090 --> 00:03:43,190 So that's what's happening over here. 83 00:03:43,190 --> 00:03:48,440 And uh, as we have discussed, this has a time complexity of O of n. 84 00:03:48,440 --> 00:03:49,490 And why is that so. 85 00:03:49,490 --> 00:03:53,060 Because you can see we are just looping or we are just traversing. 86 00:03:53,060 --> 00:03:56,840 We are only traversing the singly linked list only one time. 87 00:03:56,840 --> 00:04:02,300 So that's why the time complexity over here is O of n and the space complexity is O of one, because 88 00:04:02,300 --> 00:04:04,700 we are not using any additional space.