Data Structures in Python: Singly Linked Lists -- Merge Two Sorted Lists

In this video, we investigate how to merge two sorted singly linked lists. We first cover the general approach for how we will go about performing this action. We then implement our algorithm in Python.

The software written in this video is available at:

Do you like the development environment I'm using in this video? It's a customized version of vim that's enhanced for Python development. If you want to see how I set up my vim, I have a series on this here:

If you've found this video helpful and want to stay up-to-date with the latest videos posted on this channel, please subscribe:

[haozhang]

Great explanation, helps a lot.
I suggest adding two lines at the end of this function. self.head = new_head llist.head = None Let me Explain.
If you put 2, 3, 4, 6, 8 in the list_1 and 1, 5, 7, 9, 10 in the second list then run again. you will find the result start with 2, and the 1 is missing. This time print list2 will give you the correct answer.
because this time list1's head is pointing to 2, which is the second node in the merged linked list. Without updating self.head, we may end up with the wrong answer.

Moreover, as long as the input's head is pointed to some node in the merged list, so if someone makes changes to list2, then its actually make changes to the merged list. So from a security point of view, set the llist.head to None is important.

[debagniksen]

Really Lucid explanation, which really got me addicted with linked lists . The whole playlist is great

[karangupta]

Excellent video sir :). I was really struggling with merging 2 LL, but no I have really understood how the things are working.
Best channel on Youtube. Keep growing :)

[amankaushik]

you are ridiculously good in explaining

[chetansahu]

I want to touch your feet and thank you from the bottom of my heart. I retain loads of love and respect for you. This chapters can't be explained any easier than this.

[mightyprogrammer]

really maan!
this one was so well explained maan.

i really want to share your playlist, its helpfull and i hope you will be back soon!

[waliddib]

I think writing the code in this manner will cover the case for when L_1 is empty. it would return a merged list when you print.

if not p:
self.head = q
return

if not q:
return

[vayunandu]

there should be self.head = new_head before the return statement otherwise, it won't update the self.head with the new_head

[Obajih]

I don't think you need to make a new variable new_head, which also means you don't need to return anything at the end because self.head gets changed in beginning "ifs". You still get the same result 1-10. Still a good tutorial, thank you!


def merge_sorted(self, list2):
p = self.head
q = list2.head
s = None

if not p:
return q
if not q:
return p
elif p and q:
if p.data <= q.data:
s = p # p = self.head so this line of code is basically s = self.head
p = s.next
else:
s = q # q = list2.head so this line of code is basically s = list2.head
q = s.next

while p is not None and q is not None:
if p.data <= q.data:
s.next = p
s = p
p = s.next
else:
s.next = q
s = q
q = s.next
if p is None:
s.next = q
if q is None:
s.next = p

[yongguangqin]

Thanks again for your awesome videos. One quick observation: based on how you used the function at the end of the video, it seems that it needs to update head of the calling list?

[Ishanmahesh]

Great explaination.
I have only one doubt that what does this return new_head does ?
If I don't write it, then also it works.

[neelnair]

Thank you for the videos! One question: why do we need the return statement? We can just say self.head=new_head right?

[heidik]

Great explanation :) I just had a quick question though. It seems odd to me to return p or q in the first "if else" statement above. The reason this confuses me is because we defined those to equal the head value of the lists. So why is it that we can use those to indicate the list as a whole? (Hopefully that was somewhat clear). Cheers!

[Andhere-Ki-Aahat]

Ver well explained sir.But i am facing a doubt. if we are making s=p.next than why we are using s=p as by next also p
value is pointed in s?

[yashpandey]

Sir just a side question related to machine learning: Do I need to learn all the algorithms like Dijkstra, sorting, hashing, greedy and so on... before start learning ML?

[isaaclee]

Excellent explanation! Big thanks.
One small q: what happens to new_head? It seems that this works only if the base instance has the smaller head of the two lists, true?

[anaspatankar]

I am confused about the initial condition: so if q is not present, we return p which is basically the head of the first list. How does that return the entire list? Shouldn't the command return p give only the head value of the main list?

[aolvikash]

Awesome collection !! @LucidProgramming I have tested this script with below 2 lists where merge sorting are not working as per design, p -> 1, 5, 6, 7, 8, 14, 15, 20 -> None
Q -> 2, 3, 4, 9, 10, 11, 12 -> None. It's returning the below list - S -> 1, 2, 3, 4, 5, 7, 8, 14, 15, 20, 9, 10, 11, 12 -> None. Can you please suggest, Thanks

[dariuszspiewak]

I'm a bit late to this discussion.... but after we check if any of the lists is empty, there's no need to later put in the condition "if p and q." It's automatically TRUE at this point in the code. Similarly, the last 2 IF conditions are redundant. They do not contribute anything to the algorithm.

[rohithreddysureddy]

could u plz clarify if the code provided by u qualifies for the following question or should i be using recursive method for that.
Q) --
Merge two sorted singly linked lists without creating new nodes