Heads up! To view this whole video, sign in with your Courses account or enroll in your free 7-day trial. Sign In Enroll
Preview
Start a free Courses trial
to watch this video
In the last video we defined an implementation for the version of the split function that works on linked lists. In this video let's tackle the final portion - sorting and merging smaller linked lists.
This video doesn't have any notes.
Related Discussions
Have questions about this video? Start a discussion with the community and Treehouse staff.
Sign upRelated Discussions
Have questions about this video? Start a discussion with the community and Treehouse staff.
Sign up
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
You need to sign up for Treehouse in order to download course files.
Sign upYou need to sign up for Treehouse in order to set up Workspace
Sign up