1
00:00:01,290 --> 00:00:03,210
Hi, everyone, welcome to this new video.

2
00:00:03,240 --> 00:00:07,360
So in this video, we are going to solve this question murder case or telling list.

3
00:00:08,250 --> 00:00:14,910
So in this question, we are provided with an array of killing list and each link is basically sorted

4
00:00:14,910 --> 00:00:15,860
in ascending order.

5
00:00:16,050 --> 00:00:23,730
So if we talk about this, this is my first linked list, one four five second linked list is one three

6
00:00:23,730 --> 00:00:27,300
and four towelling list is 26.

7
00:00:27,750 --> 00:00:32,040
So basically each linked list is started in ascending order rate.

8
00:00:32,790 --> 00:00:40,650
What we need to do, given all this linked list, I need to find one link list which is sorted in ascending

9
00:00:40,650 --> 00:00:40,860
order.

10
00:00:40,860 --> 00:00:41,880
We need to merge.

11
00:00:42,480 --> 00:00:46,580
We need to merge all these linked list into one single short list.

12
00:00:46,950 --> 00:00:48,960
So what will be the single sorted link list?

13
00:00:48,970 --> 00:00:55,860
That will be one one, then two, then three, then four, then five.

14
00:00:56,520 --> 00:00:58,020
We have four actually two times.

15
00:00:58,020 --> 00:00:59,100
Right for this present.

16
00:00:59,100 --> 00:01:02,510
Two times so four, four, five and six.

17
00:01:02,760 --> 00:01:06,210
So given this input, we need to return this.

18
00:01:07,050 --> 00:01:08,570
This is the problem statement.

19
00:01:09,540 --> 00:01:11,510
Now the question is how we can do this.

20
00:01:12,630 --> 00:01:14,790
So basically it's very, very simple.

21
00:01:14,790 --> 00:01:23,220
But I'm going to use I will use prior to dequeue basically minimum heap rate in minimum.

22
00:01:23,430 --> 00:01:27,180
But I will do I will insert these three values initially.

23
00:01:28,530 --> 00:01:30,720
So I will insert node one.

24
00:01:31,650 --> 00:01:34,620
I have another node one, and then I will insert No.

25
00:01:34,620 --> 00:01:34,920
Two.

26
00:01:36,090 --> 00:01:36,480
Right.

27
00:01:36,660 --> 00:01:42,330
Let's say this is the head of the linked list and this is the tale of the linked list.

28
00:01:42,330 --> 00:01:42,740
Right.

29
00:01:43,140 --> 00:01:49,710
So what I will do, I will push the first node of all the link list, so I will push one, one and two

30
00:01:49,710 --> 00:01:50,640
into my minimum.

31
00:01:51,360 --> 00:01:51,680
Correct.

32
00:01:51,870 --> 00:01:54,450
Now what I will do, I will pick the minimum.

33
00:01:54,450 --> 00:02:00,360
I will pick the top element of the player dequeue knights over the top element, either this one or

34
00:02:00,360 --> 00:02:00,800
this one.

35
00:02:01,050 --> 00:02:03,930
So it can be either this or this because the values are the same.

36
00:02:04,380 --> 00:02:07,370
So let's say I am talking about this, this one.

37
00:02:07,650 --> 00:02:13,350
So what will happen since this is the first node, this will be the head and this will also be the deal

38
00:02:13,350 --> 00:02:14,550
right now.

39
00:02:14,550 --> 00:02:18,060
After that, what I will do, I will push the next of this.

40
00:02:18,150 --> 00:02:19,220
I will push for.

41
00:02:19,500 --> 00:02:24,990
So since I took minimum, then I will push for the next element for this.

42
00:02:25,960 --> 00:02:30,810
Right now, again, I will pick the minimum, so for one, two, which one is minimum, one year minimum,

43
00:02:30,820 --> 00:02:35,410
so remove one, I will put one here and I will make this connection.

44
00:02:35,410 --> 00:02:37,350
And this is my deal and this is my head.

45
00:02:38,650 --> 00:02:38,950
Right.

46
00:02:39,160 --> 00:02:42,430
So after picking one, the next element is three.

47
00:02:42,430 --> 00:02:43,870
So I will push three.

48
00:02:44,500 --> 00:02:44,920
Right.

49
00:02:45,070 --> 00:02:46,000
I will push three.

50
00:02:46,010 --> 00:02:48,490
Now my priority queue contains two, three and four.

51
00:02:48,490 --> 00:02:49,390
Which one is minimum.

52
00:02:49,930 --> 00:02:50,860
Two is minimum.

53
00:02:51,040 --> 00:02:54,490
So I will pop two, I will connect two.

54
00:02:55,030 --> 00:03:00,910
I will update my deal and then the next of two is basically six.

55
00:03:01,240 --> 00:03:06,850
So I will push six again for three and six a.m. three years minimum.

56
00:03:06,850 --> 00:03:10,170
So big three make the connection.

57
00:03:11,620 --> 00:03:14,740
Now what will we will make this connection right.

58
00:03:14,950 --> 00:03:16,470
Will update the tail pointer.

59
00:03:16,690 --> 00:03:19,150
What is the next of three next threes for.

60
00:03:19,300 --> 00:03:24,220
So I will insert four now again the minimum will give you the minimum.

61
00:03:24,220 --> 00:03:28,570
So for Forensic's, these two values are seen so we can pick any.

62
00:03:28,570 --> 00:03:33,610
So let's say I am picking this, so this will become four again.

63
00:03:33,610 --> 00:03:39,700
I will update my tail pointer and the next of four is basically five, so I will insert five.

64
00:03:40,510 --> 00:03:44,650
Right now I have five, four and six.

65
00:03:45,070 --> 00:03:46,090
So which one is minimum.

66
00:03:46,360 --> 00:03:47,170
Four is minimum.

67
00:03:47,170 --> 00:03:47,920
So big four.

68
00:03:50,020 --> 00:03:52,510
And what is the next or four.

69
00:03:52,660 --> 00:03:53,980
So next of four is nothing.

70
00:03:53,980 --> 00:03:55,560
So we will not push anything.

71
00:03:55,990 --> 00:04:00,130
So right now my map is containing only two elements, five and six.

72
00:04:00,640 --> 00:04:01,780
So which one is minimum.

73
00:04:01,780 --> 00:04:02,740
Five is minimum.

74
00:04:03,070 --> 00:04:04,570
So I will make the connection.

75
00:04:05,260 --> 00:04:09,730
I will update the tail pointer and release the next top five.

76
00:04:09,730 --> 00:04:12,730
Next of five is nil, so I will not push anything.

77
00:04:12,940 --> 00:04:17,079
Now my priority is only one element, so this will be the minimum element.

78
00:04:17,470 --> 00:04:18,579
I will connect to this.

79
00:04:18,850 --> 00:04:20,680
I will update my tail pointer.

80
00:04:21,579 --> 00:04:22,960
What is the next top six?

81
00:04:22,960 --> 00:04:24,580
Next of six is nil.

82
00:04:24,760 --> 00:04:28,300
So I will not push anything and your priority will become empty.

83
00:04:28,630 --> 00:04:33,610
So when your priority queue becomes empty, you are then you are done.

84
00:04:33,610 --> 00:04:34,710
And what is your answer?

85
00:04:34,720 --> 00:04:37,930
You will return head plate and this is your sorted list.

86
00:04:40,520 --> 00:04:40,920
Right.

87
00:04:40,940 --> 00:04:47,360
So we will return head, so we need to talk head so that we can return this and we need to store tail

88
00:04:47,390 --> 00:04:49,220
so that we can make connections.

89
00:04:49,790 --> 00:04:50,210
Right.

90
00:04:50,450 --> 00:04:56,750
So you can solve this problem very easily using the priority queue, because Pritikin will give you

91
00:04:56,750 --> 00:04:58,390
the minimum element each time.

92
00:04:58,400 --> 00:05:00,080
And we want a minimum element.

93
00:05:01,790 --> 00:05:05,560
So you can write the code for this function, so you can write the code for this problem.

94
00:05:05,570 --> 00:05:07,500
I will be writing the code in the next review.

95
00:05:08,150 --> 00:05:09,020
So this is it.

96
00:05:09,020 --> 00:05:10,410
I will see you in the next one.

97
00:05:10,460 --> 00:05:11,090
Thank you.

