1 00:00:00,000 --> 00:00:03,015 In the last video, we defined an implementation for 2 00:00:03,015 --> 00:00:06,589 the version of the split function that works on linked lists. 3 00:00:06,589 --> 00:00:10,275 It contained a tiny bit more code than the array or list version and 4 00:00:10,275 --> 00:00:11,421 that was expected. 5 00:00:11,421 --> 00:00:15,745 The merge function is no different because like with the split function, 6 00:00:15,745 --> 00:00:18,325 after we carry out a comparison operation, 7 00:00:18,325 --> 00:00:21,691 we also need to swap references to corresponding nodes. 8 00:00:21,691 --> 00:00:26,300 All right, let's add our merge function over here at the bottom, 9 00:00:26,300 --> 00:00:28,204 below the split function. 10 00:00:28,204 --> 00:00:33,183 So we'll call this merge, and it's going to take a left and a right. 11 00:00:33,183 --> 00:00:35,300 Now, because this can get complicated, 12 00:00:35,300 --> 00:00:38,092 we're going to document this function extensively. 13 00:00:38,092 --> 00:00:43,212 And as always, we're going to start with a docstring. 14 00:00:43,212 --> 00:00:49,361 So say that this function merges two linked lists, 15 00:00:49,361 --> 00:00:56,943 sorting by data in the nodes and it returns a new, merged list. 16 00:00:59,327 --> 00:01:04,305 Remember that in the merged step, we're going to compare values across two linked 17 00:01:04,305 --> 00:01:08,799 lists and then return a new linked list with nodes where the data is sorted. 18 00:01:08,799 --> 00:01:11,755 So first we need to create that new linked list. 19 00:01:11,755 --> 00:01:13,259 Let's add a comment in here. 20 00:01:13,259 --> 00:01:17,783 We'll say create a new linked list that 21 00:01:17,783 --> 00:01:22,177 contains nodes from, what's that? 22 00:01:22,177 --> 00:01:24,939 On new line, merging left and right. 23 00:01:24,939 --> 00:01:26,168 Okay, and then create a list. 24 00:01:26,168 --> 00:01:31,087 So merged = new LinkedList. 25 00:01:31,087 --> 00:01:33,891 To this list, we're gonna do something unusual. 26 00:01:33,891 --> 00:01:35,660 We're going to add a fake head. 27 00:01:35,660 --> 00:01:40,031 This is so that when adding sorted notes, we can reduce the amount of code we have 28 00:01:40,031 --> 00:01:43,896 to write but not worrying about whether we're at the head of the list. 29 00:01:43,896 --> 00:01:47,772 Once we're done, we can assign the first sorted node as the head and 30 00:01:47,772 --> 00:01:49,142 discard the fake head. 31 00:01:49,142 --> 00:01:53,415 Now, this might not make sense at first, but not having to worry about whether 32 00:01:53,415 --> 00:01:57,460 the new linked list already contains a head or not makes the code simpler. 33 00:01:57,460 --> 00:01:59,057 We'll add another comment. 34 00:01:59,057 --> 00:02:04,243 Add a fake head that is discarded later. 35 00:02:04,243 --> 00:02:07,319 We'll say merged.add(0). 36 00:02:07,319 --> 00:02:09,412 Like we've been doing so far, 37 00:02:09,412 --> 00:02:14,334 we'll declare a variable named current to point to the head of the list. 38 00:02:14,334 --> 00:02:19,715 Set current to the head of the linked list and 39 00:02:19,715 --> 00:02:23,646 then current = merged.head. 40 00:02:23,646 --> 00:02:29,930 Next, we'll get a reference to the head on each of the linked list, left and right. 41 00:02:29,930 --> 00:02:34,347 So we'll say obtain head nodes for 42 00:02:34,347 --> 00:02:38,163 left and right linked lists. 43 00:02:38,163 --> 00:02:44,099 And here we'll call this left_head = left.head and 44 00:02:44,099 --> 00:02:47,462 right_head = right.head. 45 00:02:51,320 --> 00:02:57,000 Okay, so with that setup out of the way, let's start iterating over both lists. 46 00:02:57,000 --> 00:02:59,746 So another comment, 47 00:02:59,746 --> 00:03:04,779 iterate over left and right as long, or 48 00:03:04,779 --> 00:03:11,192 we'll say until we reach the tail node of either. 49 00:03:11,192 --> 00:03:17,051 And we'll do that by saying while left_head or right_head. 50 00:03:17,051 --> 00:03:20,252 So this is a pattern that we've been following all along. 51 00:03:20,252 --> 00:03:24,278 We're going to iterate until we hit the tail nodes of both lists and we'll move 52 00:03:24,278 --> 00:03:29,050 this pointer forward every time so that we traverse the list with every iteration. 53 00:03:29,050 --> 00:03:32,990 If you remembered the logic behind this from the earlier version, once we hit 54 00:03:32,990 --> 00:03:37,980 the tail node of one list, if there are nodes left over in the other linked list, 55 00:03:37,980 --> 00:03:40,880 we don't need to carry out a comparison operation anymore. 56 00:03:40,880 --> 00:03:44,210 And we can simply add those nodes to the merged list. 57 00:03:44,210 --> 00:03:49,610 The first scenario we'll consider is if the head of the left linked list is none. 58 00:03:49,610 --> 00:03:52,810 This means we're already past the tail of left, and 59 00:03:52,810 --> 00:03:57,320 we can add all the nodes from the right link list to the final merged list. 60 00:03:57,320 --> 00:04:03,060 So you'll say, if the head node of left is None, 61 00:04:03,060 --> 00:04:05,722 we're past the tail. 62 00:04:05,722 --> 00:04:14,350 Add the node from right to merged linked list. 63 00:04:14,350 --> 00:04:19,727 So here we'll say if left_head is None: current.next_node, 64 00:04:19,727 --> 00:04:26,360 remember current points to the head of the merge list that we're going to return. 65 00:04:26,360 --> 00:04:29,460 So here we're setting its next node reference 66 00:04:29,460 --> 00:04:32,250 to the head node on the right link list. 67 00:04:32,250 --> 00:04:33,880 So we will say it, right head. 68 00:04:35,820 --> 00:04:43,195 Then, when we do that, we'll move the right head forward to the next node, 69 00:04:43,195 --> 00:04:48,862 so we'll say right_head = right_head.next_node. 70 00:04:48,862 --> 00:04:51,862 This terminates the loop on the next iteration. 71 00:04:51,862 --> 00:04:54,604 Let's look at a visualization to understand why. 72 00:04:54,604 --> 00:04:58,403 Let's say we start off with a linked list containing four nodes. 73 00:04:58,403 --> 00:05:02,749 So we keep calling split on it until we have lists with just a single head, 74 00:05:02,749 --> 00:05:05,187 single node linked lists essentially. 75 00:05:05,187 --> 00:05:08,960 So let's focus on these two down here that we'll call left and right. 76 00:05:08,960 --> 00:05:12,060 We haven't implemented the logic for this part yet, but here, 77 00:05:12,060 --> 00:05:16,270 we would compare the data values and see which one is less than the other. 78 00:05:16,270 --> 00:05:19,490 So we'll assume that left's head is lesser than right's head. 79 00:05:19,490 --> 00:05:23,493 So we'll set this as the next node in the final merged list. 80 00:05:23,493 --> 00:05:28,032 Left is now an empty linked list, so left.head equals none. 81 00:05:28,032 --> 00:05:30,127 On the next path through the loop, 82 00:05:30,127 --> 00:05:34,040 left_head is none which is the situation we just implemented. 83 00:05:34,040 --> 00:05:35,594 Here we can go ahead and and 84 00:05:35,594 --> 00:05:39,562 now assign right_head as the next node in the merged linked list. 85 00:05:39,562 --> 00:05:42,920 We know that right is also a singly linked list. 86 00:05:42,920 --> 00:05:44,300 Here's the crucial bit. 87 00:05:44,300 --> 00:05:49,460 When we move the pointer forward by calling next node on the right node, 88 00:05:49,460 --> 00:05:55,140 there is no node and the right link, the right link list is also empty now, 89 00:05:55,140 --> 00:05:58,790 which means that both left_head and right_head are none, and 90 00:05:58,790 --> 00:06:02,350 either one of these would cause our loop condition to terminate. 91 00:06:02,350 --> 00:06:07,040 So what we've done here is encoded a stopping condition for the loop. 92 00:06:07,040 --> 00:06:09,660 So we need to document this because it can get fuzzy. 93 00:06:09,660 --> 00:06:14,878 So right above that line of code, I'll say call 94 00:06:14,878 --> 00:06:19,841 next on right to set loop condition to False. 95 00:06:19,841 --> 00:06:23,070 Okay, there's another way we can arrive at this stopping condition, and 96 00:06:23,070 --> 00:06:26,517 that's in the opposite direction if we start with the right_head being none. 97 00:06:26,517 --> 00:06:33,486 So here we'll say I'm going to add another comment if, oops, not there, there. 98 00:06:33,486 --> 00:06:39,371 If the head node of right is None, 99 00:06:39,371 --> 00:06:43,372 we're past the tail. 100 00:06:43,372 --> 00:06:51,121 And we'll say, add the tail node from left to merged linked list. 101 00:06:51,121 --> 00:06:52,491 And then we'll add that condition. 102 00:06:52,491 --> 00:06:56,680 We'll say, elif right_head is None. 103 00:06:56,680 --> 00:07:00,330 Now remember, we can enter these even if left_head is None. 104 00:07:00,330 --> 00:07:03,000 We can still go into this condition. 105 00:07:03,000 --> 00:07:07,742 We can still enter this if statement and execute this logic because while loop, 106 00:07:07,742 --> 00:07:10,640 the loop condition here is an or statement. 107 00:07:10,640 --> 00:07:14,674 So even if left_head is false, if this returns true because there's a value 108 00:07:14,674 --> 00:07:17,725 there, there’s a node there, the loop will keep going. 109 00:07:17,725 --> 00:07:19,283 Okay, now in this case, 110 00:07:19,283 --> 00:07:24,197 we want to set the head of the left linked list as the next node on the merge list. 111 00:07:24,197 --> 00:07:28,096 So this is simply the opposite of what we did over here. 112 00:07:28,096 --> 00:07:33,524 We'll set current.next_node = left_head. 113 00:07:33,524 --> 00:07:38,030 And then we'll move, so after doing that, we can move the variable pointing to 114 00:07:38,030 --> 00:07:41,795 left head forward, which as we saw earlier is past the tail node and 115 00:07:41,795 --> 00:07:44,036 then results in the loop terminating. 116 00:07:44,036 --> 00:07:48,844 So we'll say left_head = left_head.next_node, 117 00:07:48,844 --> 00:07:52,329 and I'll add that comment here as well. 118 00:07:52,329 --> 00:07:59,260 So we'll say call next on left to set loop condition to False. 119 00:07:59,260 --> 00:08:03,110 Because here, right_head is None and now we make left_head None. 120 00:08:03,110 --> 00:08:06,782 These two conditions we looked at were either the left_head or 121 00:08:06,782 --> 00:08:11,350 right_head were at the tail nodes of our respective lists. 122 00:08:11,350 --> 00:08:16,040 Those are conditions that we run into when we've reached the bottom of our split, 123 00:08:16,040 --> 00:08:20,280 where we have single element linked list or empty linked list. 124 00:08:20,280 --> 00:08:22,830 Let's account for our final condition 125 00:08:22,830 --> 00:08:28,050 where we're evaluating a node that is neither the head nor the tail of the list. 126 00:08:28,050 --> 00:08:32,260 And this condition, we need to reach into the nodes and actually compare the data 127 00:08:32,260 --> 00:08:38,410 values to one another before we can decide which node to add first to the merge list. 128 00:08:38,410 --> 00:08:41,790 So here this is an else because we've arrived at our third condition, 129 00:08:41,790 --> 00:08:42,520 third and final. 130 00:08:42,520 --> 00:08:46,710 And here we'll say, not at either tail node, 131 00:08:48,190 --> 00:08:54,715 obtain node data to perform comparison operations. 132 00:08:54,715 --> 00:08:57,945 So let's get each of those data values out of the respective nodes so 133 00:08:57,945 --> 00:08:59,185 that we can compare it. 134 00:08:59,185 --> 00:09:04,016 So we'll say left_data = left_head.data, 135 00:09:04,016 --> 00:09:08,667 and right_data = right_head.data. 136 00:09:08,667 --> 00:09:10,315 Okay, what do we do next? 137 00:09:10,315 --> 00:09:11,750 Well, we compare. 138 00:09:11,750 --> 00:09:12,760 But first, let's add a comment. 139 00:09:12,760 --> 00:09:19,108 So we'll say if data on left is less than right, 140 00:09:19,108 --> 00:09:22,611 set current to left node. 141 00:09:22,611 --> 00:09:26,850 And then move, actually, we'll add this in a second. 142 00:09:26,850 --> 00:09:32,868 So here, we'll say if left_data is less than right_data, 143 00:09:32,868 --> 00:09:37,162 then current.next_node = left_head. 144 00:09:37,162 --> 00:09:40,074 And then we'll add a comment, and 145 00:09:40,074 --> 00:09:44,400 we'll say move left head to next node on that list. 146 00:09:44,400 --> 00:09:51,870 So we'll say, left_head = left_head.next_node. 147 00:09:51,870 --> 00:09:57,840 Just as our comment says, we'll check if the left_data is less than the right_data. 148 00:09:57,840 --> 00:10:00,682 If it is, since we want a list in ascending order, 149 00:10:00,682 --> 00:10:04,424 we'll assign the left node to be the next node in the merged list. 150 00:10:04,424 --> 00:10:08,877 We'll also move the left_head forward to traverse down to the next node 151 00:10:08,877 --> 00:10:10,485 in that particular list. 152 00:10:10,485 --> 00:10:14,755 Now if left is larger than right, then we want to do the opposite. 153 00:10:14,755 --> 00:10:17,675 So we'll go back two spaces, add another comment. 154 00:10:17,675 --> 00:10:23,002 If data on left is greater than right, 155 00:10:23,002 --> 00:10:27,833 set current to right node, okay? 156 00:10:27,833 --> 00:10:35,190 So else, here we assign the right_head to be the next node in the merged list, 157 00:10:35,190 --> 00:10:39,208 so current.next_node = right_head. 158 00:10:39,208 --> 00:10:45,152 And then comment, move right head to next node. 159 00:10:45,152 --> 00:10:53,059 So right_head = right_head.next_node. 160 00:10:53,059 --> 00:10:58,324 Okay, after doing that, we move the right_head pointer to reference in next 161 00:10:58,324 --> 00:11:03,825 node in the right list and finally, at the end of each iteration of the while loop, 162 00:11:03,825 --> 00:11:06,569 so not here but two spaces back, right? 163 00:11:06,569 --> 00:11:11,221 Make sure we're indented at the same level as the while, so we gotta go, 164 00:11:11,221 --> 00:11:15,356 yep, or not the same level as the while but the same outer scope. 165 00:11:15,356 --> 00:11:21,896 And then there we're going to say move current to next node, 166 00:11:21,896 --> 00:11:26,010 so current = current.next_node. 167 00:11:26,010 --> 00:11:29,027 Okay, don't worry if this is confusing, as always, 168 00:11:29,027 --> 00:11:31,529 we'll look at a visualization in just a bit. 169 00:11:31,529 --> 00:11:35,784 So we'll wrap up this function by discarding that fake head we set earlier, 170 00:11:35,784 --> 00:11:39,517 setting the correct node as head, and returning the linked list. 171 00:11:39,517 --> 00:11:45,106 So we'll add a comment, discard fake head, 172 00:11:45,106 --> 00:11:49,750 and set first merged node as head. 173 00:11:49,750 --> 00:11:56,042 So here we'll say head = merged.head.next_node. 174 00:11:56,042 --> 00:11:59,770 And then merged.head = head. 175 00:11:59,770 --> 00:12:02,400 And finally, return merged. 176 00:12:03,420 --> 00:12:05,480 Okay, we wrote a lot of code here. 177 00:12:05,480 --> 00:12:07,850 A lot of it was comments but still it's a bunch. 178 00:12:07,850 --> 00:12:09,170 Let's take a quick break. 179 00:12:09,170 --> 00:12:12,770 In the next video, we'll test this out, evaluate our results, and 180 00:12:12,770 --> 00:12:14,720 determine the runtime of our algorithm.