LeetCode Merge Two Sorted Lists Solution Explained - Java
Vložit
- čas přidán 20. 02. 2019
- The Best Place To Learn Anything Coding Related - bit.ly/3MFZLIZ
Join my free exclusive community built to empower programmers! - www.skool.com/software-develo...
Preparing For Your Coding Interviews? Use These Resources
--------------------
(My Course) Data Structures & Algorithms for Coding Interviews - thedailybyte.dev/courses/nick
AlgoCademy - algocademy.com/?referral=nick...
Daily Coding Interview Questions - bit.ly/3xw1Sqz
10% Off Of The Best Web Hosting! - hostinger.com/nickwhite
Follow My Twitter - / nicholaswwhite
Follow My Instagram - / nickwwhite
Other Social Media
----------------------------------------------
Discord - / discord
Twitch - / nickwhitettv
TikTok - / nickwhitetiktok
LinkedIn - / nicholas-w-white
Show Support
------------------------------------------------------------------------------
Patreon - / nick_white
PayPal - paypal.me/nickwwhite?locale.x...
Become A Member - / @nickwhite
#coding #programming #softwareengineering - Věda a technologie
For anyone wondering, a linked list is a pointer data structure. This means that when we say “node.next = l1” it is a reference to a pointer which holds the full data. As such the old “next” pointer remains as well as the value. So at the very end we are truly appending the “rest” of the non null list not just a value without a next pointer (it so happens that lines 31&36 are useless)
Could you tell me why we need a temp node and then point a current node to temp node but return the temp node... Is temp node changing along with current node? If it is then why don’t we just return current node... if it is not, then temp node is still empty so we are return an empty node. next? i’m struggling to understand this. 😭
@@xilongzhang6856 The reason we do not return current node is because, as stated in steves comment, current node is a pointer, at the end of the code, it points to the last node object, however we must return the list from the beginning. The beginning of the list is temp_node (which has value 0 , as nick instantiated it to be that) when we say '.next' it ends up pointing to the first node we added to current node. At the start of the code when we make current = temp, this makes it so we can append nodes to the list we created in temp, using the current node pointer. current and temp point to the same list, just at different positions... hope this helped
@@devsyb9174 thank you. I seee
Thanks for this explanation, it wasn't really clear in the video.
Exactly. We do not need line 31 and 36.
Those who are submitting for the first time and getting an extra 0 in front of the list, its because you are returning the address of an empty node, whereas the first element is being stored in the next node to the head node. Try returning temp_node->next
Thankyou a lot ❤️❤️
Im a third year CS student and even the easy leetcode problems make no sense to me usually. I can tell I still don't have that fundamental base yet. There is a certain level of assumed knowledge this video is going with. Oh well, I will get there : _ )
sameee bro
Hey hows it going now? Im assuming you're on your 4th and final year as a cs student? bc I, in your same position lol
This is probably an insane idea but I feel like I just wasted 3 years of my time in college studying code, while in my last 3-4 months, I've gained much more knowledge than ever studying by myself.
Wow really? I am not tryna brag, just to put it into perspective hopefully you can get motivated by what I’m about to say. I am a physics major nothing in CS, I am second year at that and I understand what pretty much every easy leetcpde problem asks of me. I use JavaScript and have only seen videos on web development. I have completed 2 easy ones so far without help. It’s easy to understand the question just implementing the code is difficult because I always want to get the cleanest code possible. I came to this video hoping he was going to show a cleaner solution but it was what I was going to put. So yeah if you can’t solve anything, let alone understand the question you really need to think about what you want in life. Either quit or be better. Hopefully it’s the latter. (Especially since you are CS major, dude you literally study these concepts in your major, the code is the least of your worries, are you like failing or not paying attention?)
@@sslvsme5763 Im now working professionally as a software engineer and I basically still feel the same way fyi. I dont need to use any of this stuff at my job.
Hi. I know about reference types (in Java or C#) but I don't understand how `head` get its value. what topics should I read about to know how its works?
3:45 "First try!"
sees attempts. :o
On a serious note, this is really helpful. Thank you so much for posting this, please keep it up!
thx I didn't notice that and almost had a breakDown cuz it didn't work well for me 😭😭😭.
awesome video. One issue though is on line #31 l1=l1.next and #36 l2=l2.next seems unnecessary
yes dude i gonna feel the samething
@@sivaganesh4489 That is redundant but it has nothing to do with the final output. That is how he got away with it.
Correct!
I think so !!
Yes, i think so
Would be much nicer if your photo wasn't covering up the code :(
thanks, nick for posting this, one suggestion front camera screen is blocking the end part of the code.
nick is so legend even my sister know him whenever she swing by my pc she's like hey thats NICK WHITE
What if after one of the lists reaches null, the other list has more than one node left in it? For example if the lists were [1,2,3,4] and [5,6,7,8] by the time the first node reaches null the second list would still have 4 more nodes to go through since all the values were larger than the larger value in the first list. With the if statements he added at the end, his program would just pull the first node off the second list and possibly leave more remaining. Wouldn't you want to implement a while loop to go through the remaining list until it reaches null?
This is addressed in my comment about the way that linked lists work
same thought.... if there are more nodes in one list then we have to traverse than last loop till we get to null
@@Godl_Damon if you have a pointer to one linked list item you have a pointer to all the items it points to. You only need the first link in the chain to have the entire chain.
@@trey8735 yeah after many problems I understood that
what is time & space complexity ?
Why we are just appending one last node in the final. What if we have 2 link list with 3 and 5 nodes. After while loop we need to append 2 items in the the final list from l2.
See my explanation above
Even if you have two nodes left, the second last node you insert still points to the correct node(the last node) since the input is already two sorted lists
How is temp_node being updated as curr updates during the traversal?
it shouldnt be update
the current should be updated only to the next
I don't understand one thing about that if condition is that it runs only once I means if L1 is null and l2 has 2 values left but the if condition only runs once so it does not go to the end please help me with my confusion
This is addressed in my comment about the way that linked lists work
Very great ! Could you please explain the l1!=null part please I dont get why we really use it?
if it's null then you have reached the end of the linked list.
@@cautioni Wouldn't that only add the very next item in l1 if l2 is empty instead of the entirety of l1? For example
l1 = [1, 2, 3, 4, 5];
l2 = [1, 2, 3];
Would this not result in the output just being [1, 1, 2, 2, 3, 3, 4] excluding the 5 since you're not accessing the 5?
I wish i could see more of the editor rather than your face.
I don't understand why you wrote the line 26 code.
Nick, it's a very good explanation, but your face covers part of the code.
Thanks so much for the video, it was very helpful! One question if you don't mind - shouldn't it be while loops on Line 29 and 34
No it doesn't have to because the rest of the answer is just whatever is left of either of the lists and since it's already linked, the whole list can just be taken.
@@MallardDuck77 thanks, had the same doubt.
@@MallardDuck77 Thank you.
@@MallardDuck77 tq brooo
I was told on the interview that I cannot create a new list and this problem got me stumped.
Shouldn't it be, l1.val
samething
1:28 why temp_node is needed
where is the temp node actually pointing to it is just an empty node
It is indeed empty until we set the value of next. As we have initially set current to temp, changes made to the data on current affect the temp values as well (we are actually using pointer data in memory)
@@stevothebeavo that's good to know! thank you for explaining!
It is showing time limit exceed
Do you have recursive solution version?
replace with an if and recall the function
I was trying this problem by sorting inplace. Without creating new list. Was stuck for so many hours 😅
The entry level interview I had, they said I could not create a new list, and I was stomped. The way I figured out was that you need to save the prev node every time. Unfortunately I was not able to find a working solution in time and got rejected.
1:24 helpful tip for linked lists
why exactly did he do that? cant we overwrite the first node with the smaller node?
@@parthpuri2000 this is a common "trick" for not modifying the algorithm due to the HEAD edge case. You will find this trick in other problems.
Thank you Nick!
why we return temp_node insteadof curr ???? why???
Because during the traversal, the temp_node is still at the beginning of the list, while curr is at the end of the list. If you return curr you will only get 1 element, but because temp_node is still at the beginning, it will return the whole list. Hope this helps.
@@lamtruong3935 so is temp being updated as curr updates during the traversal?
@@michaelsy7844 yes
is it possible to do this with space O(1)?
This solution uses constant space, lol. O(1) space or constant space means your algorithms uses the same amount of space regardless of the size of the input data. E.g. the amount of space used doesn't depend on the input. E.g. the amount of space you use doesn't scale with input. E.g. CONSTANT.
@@Brandon-oo1qi , the implementation doesn't use O(1) space complexity. The author uses another LinkedList to store the result.
Therefore the space complexity is O(m+n). And, your claim "the amount of space you use doesn't scale with input" is called linear space.
@@jugsma6676 No!! The author is not using extra space apart from just a temp and curr variables
They doesnt count as extra space because if you look carefully only once a new node is created(in start). So the space complexity is not O(m+n), it is O(1).
Although time complexity is O(m+n).
@@bharatbhatia6000 , you are right. If the program given space is O(m+n) and using O(m+n) will lead to O(1) and anything beyond that will be extra space.
What is temp_node.next pointing to? current_node?
temp_node is the dummy node which value is 0 in the code. We want the true head so we return temp_node.next. During the list traverse process, the temp_node doesn't move during the traverse.
Hey. Does anyone know how to effectively debug a linked list? for example- one could easily pause an iteration and inspect a value in vscode or in the browser console while using other data structures. what will be the best way to debug the input / output relationship in linked list.
Leetcode premium has an option to use a debugger when you run your code. This is quite useful and is also very user friendly. You could also use some of the debuggers provided within some IDE's like IntelliJ or Eclipse; you just need to install their specific pulgins.
use intellij idea for debugging in java
Can some1 explain to me why he first had to make a tempnode, and then currentnode = to tempnode... Would it be the same if I just did Listnode currentnode = new Listnode(0);
I just answered this in one of the responses to a question on my comment. Hope it helps
Currentnode is for tracking purpose. Tempnode is for returning the head node.
Thank god we have someone like neetcode, like fr man? Your webcam is blocking part of the code and you dont explain jack
Somehow i got a ZERO in the beginning of resulting list... And cannot get rid of it... Output is [0,1,1,2,3,4,4]
Riiiiigth... I returned one node before which was a zero )
your face comes cant able to see lower part of code
this was in my microsoft interview
Which country?They don't ask so easy questions in india because of competition.They ask majority questions on DP.
@@rakshitingale1460 what is DP?
@@bradjohnson8116 Dynamic Programming
thanks
Good one. Lines 31 and 36 are useless though.
I thought about it for 10 minutes. I thought I was dumb to not get why he's going to the next node.
Thanks, bro.
the problem I failed my Microsoft internship interview on
sucks man, any update on your career?!!
Great
ty ty
many of the test cases are not passing.That was not a good code
cool
Done
Lol..!! You'd submitted 2 months ago and a couple of seconds ago..!! Definitely not the first try. Though the explanation is good 😂😁
😂 😂
first try during the filming of this video
What a dumb ass comment.
FIRST TRY
first try, kek.
dude your face is covering some of the code in the bottom. So put your face somewhere.
"first try" .. right