The Conquer Step

In the last video, we defined an implementation for 0:00 the version of the split function that works on linked lists. 0:03 It contained a tiny bit more code than the array or list version and 0:06 that was expected. 0:10 The merge function is no different because like with the split function, 0:11 after we carry out a comparison operation, 0:15 we also need to swap references to corresponding nodes. 0:18 All right, let's add our merge function over here at the bottom, 0:21 below the split function. 0:26 So we'll call this merge, and it's going to take a left and a right. 0:28 Now, because this can get complicated, 0:33 we're going to document this function extensively. 0:35 And as always, we're going to start with a docstring. 0:38 So say that this function merges two linked lists, 0:43 sorting by data in the nodes and it returns a new, merged list. 0:49 Remember that in the merged step, we're going to compare values across two linked 0:59 lists and then return a new linked list with nodes where the data is sorted. 1:04 So first we need to create that new linked list. 1:08 Let's add a comment in here. 1:11 We'll say create a new linked list that 1:13 contains nodes from, what's that? 1:17 On new line, merging left and right. 1:22 Okay, and then create a list. 1:24 So merged = new LinkedList. 1:26 To this list, we're gonna do something unusual. 1:31 We're going to add a fake head. 1:33 This is so that when adding sorted notes, we can reduce the amount of code we have 1:35 to write but not worrying about whether we're at the head of the list. 1:40 Once we're done, we can assign the first sorted node as the head and 1:43 discard the fake head. 1:47 Now, this might not make sense at first, but not having to worry about whether 1:49 the new linked list already contains a head or not makes the code simpler. 1:53 We'll add another comment. 1:57 Add a fake head that is discarded later. 1:59 We'll say merged.add(0). 2:04 Like we've been doing so far, 2:07 we'll declare a variable named current to point to the head of the list. 2:09 Set current to the head of the linked list and 2:14 then current = merged.head. 2:19 Next, we'll get a reference to the head on each of the linked list, left and right. 2:23 So we'll say obtain head nodes for 2:29 left and right linked lists. 2:34 And here we'll call this left_head = left.head and 2:38 right_head = right.head. 2:44 Okay, so with that setup out of the way, let's start iterating over both lists. 2:51 So another comment, 2:57 iterate over left and right as long, or 2:59 we'll say until we reach the tail node of either. 3:04 And we'll do that by saying while left_head or right_head. 3:11 So this is a pattern that we've been following all along. 3:17 We're going to iterate until we hit the tail nodes of both lists and we'll move 3:20 this pointer forward every time so that we traverse the list with every iteration. 3:24 If you remembered the logic behind this from the earlier version, once we hit 3:29 the tail node of one list, if there are nodes left over in the other linked list, 3:32 we don't need to carry out a comparison operation anymore. 3:37 And we can simply add those nodes to the merged list. 3:40 The first scenario we'll consider is if the head of the left linked list is none. 3:44 This means we're already past the tail of left, and 3:49 we can add all the nodes from the right link list to the final merged list. 3:52 So you'll say, if the head node of left is None, 3:57 we're past the tail. 4:03 Add the node from right to merged linked list. 4:05 So here we'll say if left_head is None: current.next_node, 4:14 remember current points to the head of the merge list that we're going to return. 4:19 So here we're setting its next node reference 4:26 to the head node on the right link list. 4:29 So we will say it, right head. 4:32 Then, when we do that, we'll move the right head forward to the next node, 4:35 so we'll say right_head = right_head.next_node. 4:43 This terminates the loop on the next iteration. 4:48 Let's look at a visualization to understand why. 4:51 Let's say we start off with a linked list containing four nodes. 4:54 So we keep calling split on it until we have lists with just a single head, 4:58 single node linked lists essentially. 5:02 So let's focus on these two down here that we'll call left and right. 5:05 We haven't implemented the logic for this part yet, but here, 5:08 we would compare the data values and see which one is less than the other. 5:12 So we'll assume that left's head is lesser than right's head. 5:16 So we'll set this as the next node in the final merged list. 5:19 Left is now an empty linked list, so left.head equals none. 5:23 On the next path through the loop, 5:28 left_head is none which is the situation we just implemented. 5:30 Here we can go ahead and and 5:34 now assign right_head as the next node in the merged linked list. 5:35 We know that right is also a singly linked list. 5:39 Here's the crucial bit. 5:42 When we move the pointer forward by calling next node on the right node, 5:44 there is no node and the right link, the right link list is also empty now, 5:49 which means that both left_head and right_head are none, and 5:55 either one of these would cause our loop condition to terminate. 5:58 So what we've done here is encoded a stopping condition for the loop. 6:02 So we need to document this because it can get fuzzy. 6:07 So right above that line of code, I'll say call 6:09 next on right to set loop condition to False. 6:14 Okay, there's another way we can arrive at this stopping condition, and 6:19 that's in the opposite direction if we start with the right_head being none. 6:23 So here we'll say I'm going to add another comment if, oops, not there, there. 6:26 If the head node of right is None, 6:33 we're past the tail. 6:39 And we'll say, add the tail node from left to merged linked list. 6:43 And then we'll add that condition. 6:51 We'll say, elif right_head is None. 6:52 Now remember, we can enter these even if left_head is None. 6:56 We can still go into this condition. 7:00 We can still enter this if statement and execute this logic because while loop, 7:03 the loop condition here is an or statement. 7:07 So even if left_head is false, if this returns true because there's a value 7:10 there, there’s a node there, the loop will keep going. 7:14 Okay, now in this case, 7:17 we want to set the head of the left linked list as the next node on the merge list. 7:19 So this is simply the opposite of what we did over here. 7:24 We'll set current.next_node = left_head. 7:28 And then we'll move, so after doing that, we can move the variable pointing to 7:33 left head forward, which as we saw earlier is past the tail node and 7:38 then results in the loop terminating. 7:41 So we'll say left_head = left_head.next_node, 7:44 and I'll add that comment here as well. 7:48 So we'll say call next on left to set loop condition to False. 7:52 Because here, right_head is None and now we make left_head None. 7:59 These two conditions we looked at were either the left_head or 8:03 right_head were at the tail nodes of our respective lists. 8:06 Those are conditions that we run into when we've reached the bottom of our split, 8:11 where we have single element linked list or empty linked list. 8:16 Let's account for our final condition 8:20 where we're evaluating a node that is neither the head nor the tail of the list. 8:22 And this condition, we need to reach into the nodes and actually compare the data 8:28 values to one another before we can decide which node to add first to the merge list. 8:32 So here this is an else because we've arrived at our third condition, 8:38 third and final. 8:41 And here we'll say, not at either tail node, 8:42 obtain node data to perform comparison operations. 8:48 So let's get each of those data values out of the respective nodes so 8:54 that we can compare it. 8:57 So we'll say left_data = left_head.data, 8:59 and right_data = right_head.data. 9:04 Okay, what do we do next? 9:08 Well, we compare. 9:10 But first, let's add a comment. 9:11 So we'll say if data on left is less than right, 9:12 set current to left node. 9:19 And then move, actually, we'll add this in a second. 9:22 So here, we'll say if left_data is less than right_data, 9:26 then current.next_node = left_head. 9:32 And then we'll add a comment, and 9:37 we'll say move left head to next node on that list. 9:40 So we'll say, left_head = left_head.next_node. 9:44 Just as our comment says, we'll check if the left_data is less than the right_data. 9:51 If it is, since we want a list in ascending order, 9:57 we'll assign the left node to be the next node in the merged list. 10:00 We'll also move the left_head forward to traverse down to the next node 10:04 in that particular list. 10:08 Now if left is larger than right, then we want to do the opposite. 10:10 So we'll go back two spaces, add another comment. 10:14 If data on left is greater than right, 10:17 set current to right node, okay? 10:23 So else, here we assign the right_head to be the next node in the merged list, 10:27 so current.next_node = right_head. 10:35 And then comment, move right head to next node. 10:39 So right_head = right_head.next_node. 10:45 Okay, after doing that, we move the right_head pointer to reference in next 10:53 node in the right list and finally, at the end of each iteration of the while loop, 10:58 so not here but two spaces back, right? 11:03 Make sure we're indented at the same level as the while, so we gotta go, 11:06 yep, or not the same level as the while but the same outer scope. 11:11 And then there we're going to say move current to next node, 11:15 so current = current.next_node. 11:21 Okay, don't worry if this is confusing, as always, 11:26 we'll look at a visualization in just a bit. 11:29 So we'll wrap up this function by discarding that fake head we set earlier, 11:31 setting the correct node as head, and returning the linked list. 11:35 So we'll add a comment, discard fake head, 11:39 and set first merged node as head. 11:45 So here we'll say head = merged.head.next_node. 11:49 And then merged.head = head. 11:56 And finally, return merged. 11:59 Okay, we wrote a lot of code here. 12:03 A lot of it was comments but still it's a bunch. 12:05 Let's take a quick break. 12:07 In the next video, we'll test this out, evaluate our results, and 12:09 determine the runtime of our algorithm. 12:12