Merge 2 Sorted Lists - A Fundamental Merge Sort Subroutine ("Merge Two Sorted Lists" on LeetCode)

Key Takeaways

all right so today we are going to look at how we sort or merge two sorted lists now Alyss is an abstraction I can have a linked list I could have an array so the question on lis code is with linked lists or walkthrough will be with a linked list so I can show you how it's done and how we can like avoid some work at the end you'll see what I mean in like a little case where we exhaust one list but so the question is given two sorted lists this is very similar to my video talking about merging K sorted lists this is actually a smaller video in scope because this is the fundamental that I built off in that video merging two sorted lists this is very important for algorithms like merge sort I have a video on merge sort for algorithms like merge sort we need to know how to merge two sorted lists because what we do is we drill down to base cases and those base cases push us back upwards and we have sorted lists as we go back upwards and medium merge those after doing the split steps for this problem two sorted lists we have a sorted list how do we do this let's look at how we do this so we're gonna do this with a linked list so the thing is length las' problems are pretty tricky when I first started learning them I was horrible at like pointer manipulation and moving those pointers around to solve problems linked those problems can become very easy with practice and just like knowing the methods that we do to work with these nodes so what we're gonna do for this problem is we're going to put a pointer at the beginning of each of these lists and we're going to use a dummy head to builds this new list so this is what the setup looks like all right so we have pointers on each of our first nodes we have a dummy head I really like using dummy head nodes for limitless problems why because we do not need to worry about having an empty state on the dummy head when we're building our new list if I put a pointer cur on this head which is what we're going to do actually let me rename things so it's a little more clear so what I'm going to do is I'm going to build my list off of curve if I didn't have a dummy head what if cur is know what occur has nothing I can't just say cur Tom next because what if the actual her is not a dummy head node gets rid of this problem by when we points occur I know it's gonna have a value it's just going to be my dummy head I keep saying dummy head this is kind of annoying so I point list 1 points are here L 2 points are there we are going to advance those pointers as we eat up the parts of the list and we choose items so we perform our first comparison we want the lesser item the lesser item gets the placement if they're equal we can take it from both list one or list two negative one versus one the smaller item is going to be negative one negative one gets the placement so this is what happens so what just happened I appended the negative one node to the dummy head so now this is the first node in our list and it's the last node in our list and what I did was I moved her to this node so cur is always going to be pointing at the tail of the list we are building the tail of the sorted list we are building and I advanced L 2 and now L 2 points here and now we can continue our comparisons between l1 and l2 and advance and just stay with me it becomes very straightforward the thing about these length list problems is they're often done in M plus n time or linear time and we use constant space because it's just about rewiring it's literally like reelect wrists we're just rewiring stuff so what we do is 1 versus 2 one gets the placement because it is less so turn X we point it to list 1 and we advance list 1 and of course we advance occur to the tail of the sorted list cur always points to the tail of the sorted list and so as you can see we rewired the node kurwa sitting at 2 now points to this node and now cur hops itself to what it just pointed itself to because current needs to stay at the end of the sorted list so list 1 is sitting here list 2 is sitting here those are pointers they're pointing into the lists so 2 versus 3 2 gets the placement let's do our rewiring we advance list 2 because we just add up to one of its nodes we point this node that cur is pointing to to this node I Bakr hops on to the node is pointed to and now Kearney's who stay at details and list always that's what happens and so now do you notice how as we're going through this we're slowly building up a sorted list we start at negative one we go to one we go to two so you see it slowly we're eating up these lists through these comparisons and we're building a sorted list so now what we do is compare list one and list two again cur is sitting at the tail of the sorted list this is the sorted list this is the stuff we still are working on so now three and three hoomans so we can take it from either the list let's just take it from the list one so what we do is list one hops here we rewire the node that Curtis sitting on two points to the node that just one and now kurz got a point to the tail which is this node that is about 2.2 and again Curt always sits at the tail of the sorted list do you see how we're building a sorted list and now we continue our comparisons unprocessed territory processed territory unprocessed so now comparison three gets the placement the reverse is five three is the winner so now curve points over here this arrow gets erased curve points over here and then cur hops onto what I just pointed to and L to needs to advance because we just ate one of its nose and so now what we do is we look at l1 and l2 who is the winner the winner is altitude how to gets the placement we point cur to where l2 was and we move cur to the tail of the list for building which is the note that it is about 2.2 all right so now you see we're slowly building a sorted list and notice wait I've exhausted l2 so if I've exhausted l2 what conclusion can I make I can make the conclusion that everything from l1 and beyond is going to be greater than the last element in this list it's going to be greater than or equal to the last element in this list so I could still have a four there and I'd still tack this on so what we do is this is a linked list so all we need to do is I arrange this pointer I point to l1 I points to where l1 is pointing because we made the conclusion all these nodes must be greater and as you can see they are going to be greater than the element which is for we can make that 504 it still be greater than or equal to it so what I do is I point this note to l1 and then I am finished because I have exhausted the second list and I know that the first list is all going to be in the right place and so this is how our algorithm works and this is our final linked list so let's write it out so at the end of our function all we do is hey we have a reference to the dummy head point the dummy hat next return the value of dummy head next return the pointer to this note when we have the pointer to this node then bang we have our whole list negative 1 1 2 3 3 4 5 10 15 and this is how you merge a sorted list so this is just how we would do it with an array although with linked list is kind of easier because I can just do that pointer I could just adjust that pointer and then bang I have the first list in place first list is finished and we know it's going to be greater than this last item that is how you merge two sorted lists so now let's look at time complexity we always declare our variables when we're doing Big O so M is the length of the first list and is the length of the second list you can swap those I don't know why I put it in this order I shouldn't mean anything Swan anyway but M comes before and in alphabetical order but we use n more often so I would assume that guess precedence so the time complexity is going to be Big O of M plus and at worst we traverse the length of both of those lists if they're very similar we're going to have to do a lot of comparisons and then we'll go towards detail if they're very different if I have a list of 1 2 & 3 and then the other list is all values greater than 10 then I'm going to terminates very quickly and just do the rewiring and then jump out of there because I'm finished we're going to be using constant space we're going to be using constant space because all we're doing is shifting of pointers jumping around doing our little rewiring and then getting out of there we're not creating a whole new array we're not create who knows we're not creating an array we're not creating anything that will scale as our input gets arbitrarily large which is what's big o is about what these complexities and asymptotic analysis is about if you like this video if this was a clear explanation hit the like button subscribe I know that this video was kind of easy but the thing is we'll have our fair share of hourly code horns and Li code mediums we'll get to those and do those but I want to set a fundamental basis and teach these because it is key to have these fundamentals for our sorting algorithms and apply to other questions like merge K sorted lists that's all for this video [Music]