In the last video, we defined an implementation for

the version of the split function that works on linked lists.

It contained a tiny bit more code than the array or list version and

that was expected.

The merge function is no different because like with the split function,

after we carry out a comparison operation,

we also need to swap references to corresponding nodes.

All right, let's add our merge function over here at the bottom,

below the split function.

So we'll call this merge, and it's going to take a left and a right.

Now, because this can get complicated,

we're going to document this function extensively.

And as always, we're going to start with a docstring.

So say that this function merges two linked lists,

sorting by data in the nodes and it returns a new, merged list.

Remember that in the merged step, we're going to compare values across two linked

lists and then return a new linked list with nodes where the data is sorted.

So first we need to create that new linked list.

Let's add a comment in here.

We'll say create a new linked list that

contains nodes from, what's that?

On new line, merging left and right.

Okay, and then create a list.

So merged = new LinkedList.

To this list, we're gonna do something unusual.

We're going to add a fake head.

This is so that when adding sorted notes, we can reduce the amount of code we have

to write but not worrying about whether we're at the head of the list.

Once we're done, we can assign the first sorted node as the head and

discard the fake head.

Now, this might not make sense at first, but not having to worry about whether

the new linked list already contains a head or not makes the code simpler.

We'll add another comment.

Add a fake head that is discarded later.

We'll say merged.add(0).

Like we've been doing so far,

we'll declare a variable named current to point to the head of the list.

Set current to the head of the linked list and

then current = merged.head.

Next, we'll get a reference to the head on each of the linked list, left and right.

So we'll say obtain head nodes for

left and right linked lists.

And here we'll call this left_head = left.head and

right_head = right.head.

Okay, so with that setup out of the way, let's start iterating over both lists.

So another comment,

iterate over left and right as long, or

we'll say until we reach the tail node of either.

And we'll do that by saying while left_head or right_head.

So this is a pattern that we've been following all along.

We're going to iterate until we hit the tail nodes of both lists and we'll move

this pointer forward every time so that we traverse the list with every iteration.

If you remembered the logic behind this from the earlier version, once we hit

the tail node of one list, if there are nodes left over in the other linked list,

we don't need to carry out a comparison operation anymore.

And we can simply add those nodes to the merged list.

The first scenario we'll consider is if the head of the left linked list is none.

This means we're already past the tail of left, and

we can add all the nodes from the right link list to the final merged list.

So you'll say, if the head node of left is None,

we're past the tail.

Add the node from right to merged linked list.

So here we'll say if left_head is None: current.next_node,

remember current points to the head of the merge list that we're going to return.

So here we're setting its next node reference

to the head node on the right link list.

So we will say it, right head.

Then, when we do that, we'll move the right head forward to the next node,

so we'll say right_head = right_head.next_node.

This terminates the loop on the next iteration.

Let's look at a visualization to understand why.

Let's say we start off with a linked list containing four nodes.

So we keep calling split on it until we have lists with just a single head,

single node linked lists essentially.

So let's focus on these two down here that we'll call left and right.

We haven't implemented the logic for this part yet, but here,

we would compare the data values and see which one is less than the other.

So we'll assume that left's head is lesser than right's head.

So we'll set this as the next node in the final merged list.

Left is now an empty linked list, so left.head equals none.

On the next path through the loop,

left_head is none which is the situation we just implemented.

Here we can go ahead and and

now assign right_head as the next node in the merged linked list.

We know that right is also a singly linked list.

Here's the crucial bit.

When we move the pointer forward by calling next node on the right node,

there is no node and the right link, the right link list is also empty now,

which means that both left_head and right_head are none, and

either one of these would cause our loop condition to terminate.

So what we've done here is encoded a stopping condition for the loop.

So we need to document this because it can get fuzzy.

So right above that line of code, I'll say call

next on right to set loop condition to False.

Okay, there's another way we can arrive at this stopping condition, and

that's in the opposite direction if we start with the right_head being none.

So here we'll say I'm going to add another comment if, oops, not there, there.

If the head node of right is None,

we're past the tail.

And we'll say, add the tail node from left to merged linked list.

And then we'll add that condition.

We'll say, elif right_head is None.

Now remember, we can enter these even if left_head is None.

We can still go into this condition.

We can still enter this if statement and execute this logic because while loop,

the loop condition here is an or statement.

So even if left_head is false, if this returns true because there's a value

there, there’s a node there, the loop will keep going.

Okay, now in this case,

we want to set the head of the left linked list as the next node on the merge list.

So this is simply the opposite of what we did over here.

We'll set current.next_node = left_head.

And then we'll move, so after doing that, we can move the variable pointing to

left head forward, which as we saw earlier is past the tail node and

then results in the loop terminating.

So we'll say left_head = left_head.next_node,

and I'll add that comment here as well.

So we'll say call next on left to set loop condition to False.

Because here, right_head is None and now we make left_head None.

These two conditions we looked at were either the left_head or

right_head were at the tail nodes of our respective lists.

Those are conditions that we run into when we've reached the bottom of our split,

where we have single element linked list or empty linked list.

Let's account for our final condition

where we're evaluating a node that is neither the head nor the tail of the list.

And this condition, we need to reach into the nodes and actually compare the data

values to one another before we can decide which node to add first to the merge list.

So here this is an else because we've arrived at our third condition,

third and final.

And here we'll say, not at either tail node,

obtain node data to perform comparison operations.

So let's get each of those data values out of the respective nodes so

that we can compare it.

So we'll say left_data = left_head.data,

and right_data = right_head.data.

Okay, what do we do next?

Well, we compare.

But first, let's add a comment.

So we'll say if data on left is less than right,

set current to left node.

And then move, actually, we'll add this in a second.

So here, we'll say if left_data is less than right_data,

then current.next_node = left_head.

And then we'll add a comment, and

we'll say move left head to next node on that list.

So we'll say, left_head = left_head.next_node.

Just as our comment says, we'll check if the left_data is less than the right_data.

If it is, since we want a list in ascending order,

we'll assign the left node to be the next node in the merged list.

We'll also move the left_head forward to traverse down to the next node

in that particular list.

Now if left is larger than right, then we want to do the opposite.

So we'll go back two spaces, add another comment.

If data on left is greater than right,

set current to right node, okay?

So else, here we assign the right_head to be the next node in the merged list,

so current.next_node = right_head.

And then comment, move right head to next node.

So right_head = right_head.next_node.

Okay, after doing that, we move the right_head pointer to reference in next

node in the right list and finally, at the end of each iteration of the while loop,

so not here but two spaces back, right?

Make sure we're indented at the same level as the while, so we gotta go,

yep, or not the same level as the while but the same outer scope.

And then there we're going to say move current to next node,

so current = current.next_node.

Okay, don't worry if this is confusing, as always,

we'll look at a visualization in just a bit.

So we'll wrap up this function by discarding that fake head we set earlier,

setting the correct node as head, and returning the linked list.

So we'll add a comment, discard fake head,

and set first merged node as head.

So here we'll say head = merged.head.next_node.

And then merged.head = head.

And finally, return merged.

Okay, we wrote a lot of code here.

A lot of it was comments but still it's a bunch.

Let's take a quick break.

In the next video, we'll test this out, evaluate our results, and

determine the runtime of our algorithm.