1
00:00:00,750 --> 00:00:07,080
Let's now go ahead and do the second part, which is insert a node at a desired position.

2
00:00:07,080 --> 00:00:09,570
The node and the position are given.

3
00:00:09,570 --> 00:00:11,550
The linked list is zero indexed.

4
00:00:11,550 --> 00:00:16,680
If a given node is a node existing in the linked list, shift it to the desired position.

5
00:00:16,680 --> 00:00:17,970
So this is the question over here.

6
00:00:17,970 --> 00:00:23,070
Now the difference between the previous method which we have written, which is insert before was that

7
00:00:23,070 --> 00:00:26,850
at that point the position was specified in terms of a node.

8
00:00:26,850 --> 00:00:30,360
But over here it's going to be a position something like zero or 1 or 2.

9
00:00:30,360 --> 00:00:33,750
And then it's also mentioned that the linked list is zero indexed.

10
00:00:33,750 --> 00:00:39,330
Now if you're getting this question in the interview, ensure that you ask sufficient clarifying questions.

11
00:00:39,330 --> 00:00:46,380
Now a possible question could be if a linked list has only three indices, and if position is given

12
00:00:46,380 --> 00:00:47,820
as ten, what should happen?

13
00:00:47,820 --> 00:00:49,710
So that means there are just three nodes.

14
00:00:50,400 --> 00:00:52,290
And this is the linked list.

15
00:00:52,320 --> 00:00:53,700
Now it's a doubly linked list.

16
00:00:53,700 --> 00:00:55,950
So it's going to point in both directions.

17
00:00:56,660 --> 00:00:58,880
So we have both directions over here.

18
00:00:59,470 --> 00:01:01,960
And then the position is mentioned as ten.

19
00:01:01,960 --> 00:01:03,280
So what should happen now?

20
00:01:03,280 --> 00:01:07,960
Let's say the interviewer says in that case insert the given node at the tail.

21
00:01:07,960 --> 00:01:08,530
All right.

22
00:01:08,530 --> 00:01:10,000
So let's go ahead with that.

23
00:01:10,000 --> 00:01:16,270
And another possible question could be what should happen if the doubly linked list is empty and a node

24
00:01:16,270 --> 00:01:18,520
is given to be inserted at a position?

25
00:01:18,520 --> 00:01:23,470
Now let's say the interviewer replies and says to you that in this case, just make that particular

26
00:01:23,470 --> 00:01:27,100
head the the just make that particular node as the head.

27
00:01:27,100 --> 00:01:27,730
All right.

28
00:01:27,730 --> 00:01:30,940
So let's say this is the clarification received.

29
00:01:30,940 --> 00:01:33,310
Now let's go ahead and write a few test cases.

30
00:01:33,310 --> 00:01:36,250
Now we have two possible scenarios.

31
00:01:36,250 --> 00:01:39,100
For example let's say this is the doubly linked list.

32
00:01:39,100 --> 00:01:42,760
And let's say position is given as zero and the node is two.

33
00:01:42,760 --> 00:01:46,660
So you can see over here that the node is part of the doubly linked list.

34
00:01:46,660 --> 00:01:52,390
So it's mentioned that in this case we have to just shift its position of this particular node to the

35
00:01:52,390 --> 00:01:53,140
given position.

36
00:01:53,140 --> 00:01:58,060
So the output has to be 2134 and two would be at the head.

37
00:01:58,060 --> 00:01:58,300
Right.

38
00:01:58,300 --> 00:02:00,160
Because this is moved to position zero.

39
00:02:00,160 --> 00:02:01,090
And this is zero right.

40
00:02:01,090 --> 00:02:03,220
This is 012 and three.

41
00:02:03,220 --> 00:02:08,650
Now let's say another possibility is let's say position is given as three and the node is still two.

42
00:02:08,680 --> 00:02:11,890
So in that case the output should be 134 and two.

43
00:02:11,920 --> 00:02:14,890
So you can see that you have 012 and three.

44
00:02:14,890 --> 00:02:19,090
So the given node which is two is moved to position three.

45
00:02:19,120 --> 00:02:23,440
Now let's say the position is mentioned as two and the node is still two itself.

46
00:02:23,440 --> 00:02:27,250
The output which is expected would be 132 and four.

47
00:02:27,250 --> 00:02:29,740
And you can see over here you have zero one and two.

48
00:02:29,770 --> 00:02:32,440
So the node two is at index two.

49
00:02:32,470 --> 00:02:38,680
Now these are the possibilities where the given node is part of the doubly linked list.

50
00:02:38,680 --> 00:02:41,380
And then this is the case where we are shifting to the head.

51
00:02:41,380 --> 00:02:44,050
And then over here we are shifting the node to the tail.

52
00:02:44,050 --> 00:02:47,770
And then this is a case where we are shifting the node to somewhere in between.

53
00:02:47,770 --> 00:02:50,050
So these are three possibilities.

54
00:02:50,050 --> 00:02:55,210
Now you can also have possibilities where the given node is not part of the doubly linked list.

55
00:02:55,210 --> 00:02:59,770
For example, let's have this node over here which is not part of this doubly linked list.

56
00:02:59,770 --> 00:03:02,320
And then let's say the position is given as zero.

57
00:03:02,320 --> 00:03:04,600
In that case you would have to make it the new head.

58
00:03:04,600 --> 00:03:06,670
So you have 51234.

59
00:03:06,670 --> 00:03:09,460
And then both of these extremes are pointing to null.

60
00:03:09,460 --> 00:03:14,740
And then another possibility is let's say the position is mentioned as three and the given node is five.

61
00:03:14,740 --> 00:03:19,030
So in that case the output expected would be one, 235 and four.

62
00:03:19,030 --> 00:03:22,720
You can see this is position 3012 and three.

63
00:03:22,720 --> 00:03:24,790
So you have five at position three.

64
00:03:24,790 --> 00:03:28,480
So we have understood the question and we have written a few test cases.

65
00:03:28,480 --> 00:03:32,950
Now let's go ahead and discuss the method by which we can solve this question.