Merge 2 Sorted Lists - A Fundamental Merge Sort Subroutine ("Merge Two Sorted Lists" on LeetCode)
Vložit
- čas přidán 23. 01. 2019
- Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: Given two lists that are sorted, merge them into a single sorted sequence as efficiently as possible.
The key with linked list problems is pointers. Most of what we will do will be O(n) time and O(1) space.
It is all about hardwiring things together and moving pointers around, have a strong understanding of techniques to advance, stash, and move references around.
Approach 1 (Brute Force)
Append the lists together and then sort the lists.
The best we can do with this is O( n * log(n) ) because we will only know the total ordering property of the lists which lets us use (Mergesort or Quicksort, etc.)
Approach 2 (Use Pointers And Rewire Lists)
Huge tip. When building a new list while doing linked list problems dummy heads are your best friend. They prevent you from having to do null checks on a list and you can immediately append to the .next value through a pointer to it with no fear of a null pointer exception.
We just keep:
1.) a pointer to the last item in the new list we are building
2.) a pointer into the first list
3.) a pointer into the second list
We then do pair comparisons and advance accordingly.
Complexities
Time: O( m + n )
Let n be the length of list 1.
Let m be the length of list 2.
This is the worst case. We will be traversing the whole length of the lists in the case where they are nearly similar in length and value comparison results (aka we don't exhaust a list early before another).
Best case is O( min( m, n ) ) because we will only traverse as far as we need to exhaust the shorter of the lists, then we just append the rest of the other onto the result since it will all be greater than the exhausted list by default.
Space: O( 1 )
We are only working with pointers. We are using the existing nodes given to us.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is number 8.1 in "Elements of Programming Interviews" by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash. - Věda a technologie
Table of Contents:
The Problem Introduction 0:00 - 1:06
Merging The Lists: Walkthrough 1:06 - 5:51
We Have Exhausted The 2nd List 5:51 - 6:48
The Merging Is Finished 6:48 - 7:39
Time Complexity 7:39 - 8:25
Space Complexity 8:25 - 8:51
Wrap Up 8:51 - 9:16
The code for this problem is in the description. For both the iterative and recursive approaches. Fully commented for teaching purposes.
I do not see the code
Thank you, dude! I was asked this question in my interview with Microsoft and I killed with no mercy!
yuh yuh
You're an excellent educator and will be one of the reasons I find a good job. Thank you.
nice. Wish you a great life
How is your life as a programmer going?
Oh man I never realized the dummy technique before. This makes life so much easier than a nullptr and a conditional one hits every time!
yeah
This was a great explanation! Really helped me understand the concepts, thanks!
Thank you for your videos and your enthusiasm is definitely infectious! I have never been so eager to solve LinkedList problems 😂
this was by far the clearest explaination I have seen on this problem. Thank you
You are SO good at explaining these algorithms! Thank you for sharing.
sure
You are great !
Had trouble understanding mergesort stuff before this.
You made everything crystal clear
great
All of your videos are a joy to watch and helpful. Really insightful and well explained. You are awesome. Best of luck with your channel, I think you will do great.
Thanks a lot!
Thank you. Very long way to go...I can't be content.
Awesome content. Keep up the good work my man!
These videos are so good! Thank you again for providing these.
sure
10/10 whiteboard explanations are the best and most intuitive way to learn!
hey
I'm learning so much from your videos. Thank you and keep it up!
ok
You bodied this explanation. Thank yoooou!
I FINALLY GOT IT! Thank you!!
After being in the industry for 10 years and barely using any data structure, it feels good to learn about DS again.
Super useful video for my computer science test - just subscribed
This is awesome. Thank you, my man
sure
Sir You are the best ever tutor on CZcams in the sense of interest that you create in the mind of the student.. Exception to the tutors who make coding boring
thanks haha
Man please keep uploading regularly don't take a break...because bro we want to study from you...on a regular basis...
hahahahahaha, yeah I've been busy with work at Twitter - I get home at like 6 normally and then I answer email and then it is 7 and then I'm tired so I read and then it is 8....so yeah, I'm here....I'll be in school soon so I'll make videos part-time again & make a structured course
@@BackToBackSWE yo our saviour is back...bro really please make a video on how to flatten a linked list...
@@pranjalchandel3732 hahaha ok
So clear how the cur is used as a navigator and thats why we return dummy.next! love it things are clicking :)
may you flourish
Best explanation I've ever seen.
well explained. thanks
Immensely helpful. Thank you so much.
Great videos. The shmedium t shirts are an added benefit
This makes it too much easy to understand, thakyou and keep up
thanks
Thank you!
Thanks man keep up the good work :)
thanks
What a genius!!
This was so helpful!
sure
very clear! useful for me to understand the concept!!!!
Glad it was helpful! 😄 Also check out our FREE DSA Interview Prep Mini-Course - backtobackswe.com/ 🎉
yo this explanation was so good. thanks man!
Glad it helped 😄 Also check out our Free 5 Day DSA Interview Prep Mini-Course - backtobackswe.com/ 🎉
Man you are a awesome teacher🙌🙌
Man you are truly awesome
thanks
Cheers! :)
Share your wonderful video in the leetcode discuss again!
Thanks
Thanks for the video! Just one question since I've worked with pointers in C and I'm just curious how the "pointers" in python work. Is setting head = cur similar to making head point to cur? Thanks!
Amazing video, thank you so much.
Thank you 😄 We'd love for you to check out our Free 5 Day DSA Interview Prep Mini-Course - backtobackswe.com/ 🎉
Superb!
I've watched a bunch of videos on this LC question and they just write code without any depth. This brother is a great instructor (I can tell, I was a teacher). Keep up the great work yo!
thank you so much! There are other questions at - backtobackswe.com/ - Would love some feedback
@@BackToBackSWE You're welcome! Funny you mentioned that, I purchased a lifetime subscription on your platform.
My goal is to join a big tech company in the next 6-12 months. I will comment here when I make that happen.
Amazing. All the best, just waiting for your comment now 💯🎉 keep us posted
Great explanation man.
thx
thank you
bruh the way you music Interrupted you in the end killed me xD
Dude you are awesome
thanks
Thank you so much
Awesome! Do try our free mini course backtobackswe.com/
Very good explanation :)
thanks
Thanks for sharing
sure
amazing sir
Thanks
Can’t believe you’re only a sophomore man! I’ve pretty much watched every video in this series for the most part and I got 2 questions (not related to the video lol):
1) What do you think would be your dream company you would want to go to as a new grad?
2) how did you get so good at Leetcode lol
1.) Not sure. I'm less concerned about my future and MUCH more concerned about the future of Back To Back SWE. I want this to be the largest channel/resource for this in the world and...that is not a small task to undertake for anyone. So yes...that keeps me up at night...basically every night.
2.) I explain how in the video "How To Get A Job At Google", the main video on this channel. A lot of pain and suffering alone behind a computer screen. Doing problems, reading EPI (Elements of Programming Interviews) several times.
I mean...I don't get paid for this (ads make nothing, trust me...at least right now), each video takes at least 4 hours to do, the problems are dry...what else can keep a human going doing this if it is not beyond the traditional reward system? (money, adoration, etc.)
I see this channel's completion as a purpose that must happen. I can rest after but as long as there are other "past me's" in the world without a guide...I can't feel ok with myself.
Back To Back SWE wow man thank you for making that dedication. I definitely see this channel as becoming the main resource channel for interviewing. You have a way of explaining that’s really easy to follow compared to other channels. Keep up the great work!
@@airysm 👍
Great explanation. Can you do a video on "Flatten Nested List Iterator"?
I think it is in the list of 250 questions.
Dude you just explained that shit so well
Haha Really glad to help 🎉 Do you know about our 5-Day Free DSA Mini Course? Check it out here - backtobackswe.com/
Hi sir, could you please explain why dummy_head works? I mean, the curr pointer moves one step each, and dummy_head = curr, so why dummy_head didn't move at all? Thank you so much, have a great weekend!
Although I just finished that problem in very similar way I find this video super helpful. Like you mentioned, Linked List is confusing but you make it very clear. Keep up with the amazing work!
Tricky until you do a lot of them, yeah. Thank you.
Nice! one. just a small correction on time complex : I think time taken by the function would be O(n) where n is the length of the smallest list.
WHY?
here is the thing...
we are traversing the the list until one list get exhausted. once we know there is no list to compare we simply pointing to the other list, and we know other list would be the sorted, and that is constant operation.
Open for discussion.... :)
For big O you consider the worst case, which means you exhausted both linked lists. Therefore, it would be O(m + n).
Can you please explain where in the code the pointer for dummy head is set to the first element of the sorted list? Everything else except for that makes sense to me. Thanks!
What do you mean?
so are we breaking the original two lists or we are building a brand new list?
7:51 the struggle lol
but its true, whenever there is a number variable i always use n first because "numbers" duh ..
What did I say
Thanks, got a quick question if you could answer. If we have two sorted arrays of the same length n, then in order to merge them like you taught us we will have to make 2n-1 comparisons right? That means that the total steps needed are 2n-1 and not 2n. Is this correct? Thanks in advance.
Yeah I think? Fuzzy memory
@@BackToBackSWE Yeah you answered this question in detail during the mergesort video that I watched afterwards. Thank you !
I am new to programming. Could someone please tell me why we need to do this practice? In python, we have functions to merge and sort lists.
I have a question: how does dummy change?
I get it that 'cur' and 'dummy' are pointing to the same object, but not clear about how they are linked exactly.
Or maybe asking in this way:
What does 'cur=cur.next' and 'cur.next=l1' do to dummy respectively?
Thank you!
curr advances as we merge the lists. The dummy heads always stay stationary. These are pointers to memory locations.
curr.next points to a new memory location. curr points to a new memory location (where curr.next sits). the dummy head never changes what it references to.
Thank you for the explanation. But still a little puzzled. How does dummy change?
I understand that dummy stays stationary but how come it is like expanding?
@@yichuanfeng4491 That's why we return dummy.next which gives you the connections curr has made throughout the two linked lists, starting from the dummy head.
struggling with big O stuff. Don't you take up n + m space if you're given two arrays as input and you initialize a couple linked lists from the arrays?
Yes, but here we are given linked lists and we just rewire them.
@@BackToBackSWE OK, thanks. Love what you're doing. Keep it up. It's huge.
@@Hizzle182 ok haha
Ilyyyy
hey
In
if(l1.val < l2.val){
dummy.next = l1;
l1 = l1.next;
}
why isn't it that the entire list is apended to cur.?
But when you finish the loop because one list is null and you do
if(l1 == null){
dummy.next = l2;
}
then all of a sudden the entire l2 list appends itself to cur. I'm confused in leetCode if ListNode is a pointer or if it represents the entire list?
It is a linked list, the nodes are linked like a chain. Think on it
So, it's not like we remove anything from the lists to put them inside a dummy list. We simply change where each node is pointing towards to end up with one dummy list and no more list1 and list2?
Plus, everytime we have to do the manipulation of pointing cur, THEN moving it?
Hey, where is the code i'm not able to find it in desc?
The repository is deprecated - we only maintain backtobackswe.com now.
From your code -
current.next = p1 != null ? p1 : p2;
This is just an OR operation, right?
It is a ternary operator: tutorials.jenkov.com/java/ternary-operator.html
Im confused you said you that you cant build a list off cur if cur is none, but in other videos I have seen lists built off cur when cur is none :)
What if you are merging two lists in a merge sort and the lists have an element in common?
When comparing if the value from L1 is lower than L2 it will return false, because the value are equals. So, you move to the else statement that will get the value from the L2.
Please, can someone paste the code as a reply here?
The repository is deprecated - we only maintain backtobackswe.com now.
First 😁
hey
you need more interaction with the whiteboard, the whiteboard is an extension in real time of your verbal explanation, not to happen at t-1 time
ok
Is there a written solution to this?
You can check out the code repository on backtobackswe.com/