@Kevin Thanks for making this video. Just a quick thing to point the time complexity in the worst case will be O(M+N) as we may have to iterate all the values in both the lists, this happens when the values in the lists are of same range.
@@bosteador Yeah they don't mention it explicitly - they just sort of let you do your own thing and ask you questions as to why you're doing what you're doing and how you could improve it etc.
You got asked an easy question at facebook? Although leetcode has some 'hard' easy problems, I was expecting much more advanced/sophisticated than this question
@Kevin, Really like your coding walk through style! Could you please add to your list some of Leetcode problems: Longest Palindrome Substring(#5), Minimum Window Subsequence(#727), Minimum Window Substring(#76), Longest continuous increasing subsequence(#674). I know its a huge list but would really like to see your thought process :) BTW, problem explanation is so good. Thanks!
Hi ! My question is only about this last part : if(l1!=null){ dummy.next=l1; } if(l2!=null){ dummy.next=l2; } Doesn't this block of code logically take care of the numbers which haven't been added in the while loop ? For example our lists are : list1=[1,2,4] list2=[1,3,4,7,8,9] So the while loop will form the list=[1,1,2,3,4,4] and the rest will be added by the block : if(l2!=null){ dummy.next=l2; } My question is : doesn't that block add only one node ? Because it would be able to add multiple nodes . It would be in my opinon something like this : while(l2!=null){ dummy.next=l2; l2=l2.next; } What is the logic mistake that I made ? Thank you in advance!
I was not able to do this on my own, i am not sure but it doesn't look that tough but I was still not able to :/. Guilty Feels max lmao PS: Thanks for the explanation!
Both the time and space complexity will be O(n+m). n represents the number of elements in L1 and m represents the elements in L2. Because we are creating extra space, the space complexity will also be O(n + m)
I believe the time complexity should be O(min(n,m)) whichever list is smallest determines the loop range after that we exit and just set the result node next to the remaining list node
Great video, Kevin! I have a question regarding the runtime analysis though. I think what you described in the video is correct, but the caption is wrong. The runtime complexity should be O(M+N) in the worst case, where M, N are the lengths of the two list. If the two lists have smaller values alternatively (e.g. one is 1->3->5->7, while the other one is 2->4->6->8), then you have to iterate through both lists.
if these ListNodes were pointers and we created dummy = new ListNode(-1); then would it make sense to delete that dummy node from memory before returning head->next?
nishant singh thanks Nishant! If you like my explanations be sure to join the interviewing service I created thedailybyte.dev/?ref=kevin I recommend joining a premium plan if you can!
Hi. I know about reference types (in Java or C#) but I don't understand how `dummy` get its value. what topics should I read about to know how its works?
Hi Kevin! Great videos! Thank you so much for your explanations. I'm a bit confused though. So on line 15 and line 18 when you do : dummy.next =l1 (and l2 respectively), does it not append everything left in list L1 or L2 to the dummy list (just as it would in line 25 and 27 respectively?)
I have the same doubt. I think to add all remaining elements in l1 or l2, we will have to use one more while loop. It would be great if Kevin clarifies it.
Hello, L1 isn't a value, it is a node. A node has references to each other item in the list. At the beginning when we loop through and put items in individually, that happens because we splice in other nodes after them which changes the references. At the end, where we just put in either L1 or L2, the references remain intact, so all the remaining values get put into the list as well. Hope that helps!
Hey Kevin!! Big Fan of your videos and you've helped me a lot while preparing for my interviews, can you please make a video on 'Reverse Nodes in k-Group' Leetcode problem?
Hi Kevin. Great video. I love how you explain these problems. I do have one question though. I am a second year CS student who just learned about linked lists. In my class we created a new node object every time we added to our linked list. So for example, if we had 5 items in our linked list there would be 5 objects each pointing to the previous object in the list. It seems like in your code you are just changing the values in your dummy list without creating new objects. I was wondering if you could explain how the dummy list is being appended in your code without creating new objects?
It's been almost a year so I'm sure you understand this now but in case anyone else had the same question: Your teacher created multiple new Nodes because he was starting from scratch. In this case we are given Nodes to work with. So if we work with the same scenario that Kevin has in this video, if have two ListNodes being passed into our function. These two ListNodes can look something like: l1 = 1 -> 2 -> 3 l2 = 1 -> 3 -> 4 Keep in mind that although we are just showing numbers here you should really think of the numbers encased in a 'ListNode' object. When we create a new dummy ListNode in our code: ListNode dummy = new ListNode(-1), we now have something that looks like this: -1 -> null Now our next variable in our ListNode class holds a ListNode object. So if you want to assign a value to our next variable you can do something like l1.next = new ListNode(5) (We're creating a new ListNode object and assigning our next variable to it) However we also have our other ListNodes, l1, and l2, these are ListNode objects that have already been instantiated (created). So we know our next variable holds ListNode objects and l1 which currently holds the value 1 is a ListNode object so we can just go dummy.next = l1; (since l1 is a ListNode object) So now dummy looks like -1 -> 1 -> 2 -> 3
Your approach is correct but I guess in the final if-else block where we check if there are any more elements left in either of the two lists, there we need to use while loop inside our if / else block to check how many more elements are still left either in list1 or list2 after one of the list reaches to null in our upper while loop. And we also need to move dummy = dummy.next in the bottom if-else block along with the l1 = l1.next || l2 = l2.next
That's the same thing I just asked about . Here was my comment : Hi ! My question is only about this last part : if(l1!=null){ dummy.next=l1; } if(l2!=null){ dummy.next=l2; } Doesn't this block of code logically take care of the numbers which haven't been added in the while loop ? For example our lists are : list1=[1,2,4] list2=[1,3,4,7,8,9] So the while loop will form the list=[1,1,2,3,4,4] and the rest will be added by the block : if(l2!=null){ dummy.next=l2; } My question is : doesn't that block add only one node ? Because it would be able to add multiple nodes . It would be in my opinon something like this : while(l2!=null){ dummy.next=l2; l2=l2.next; } What is the logic mistake that I made ? Thank you in advance!
You have used && , so it comes out only if both the condition is false but the if condition will be false because when we are out of the while loop both the l1 and l2 will be null, I guess you should have used || condition
You can also do or operation, but suppose the smaller list got exhausted in while loop, then you can simply append the remaining big list in single operation to improve performance. Never doubt Kevin naughton
Exactly my question. I believe need to add - elseif (and thereby third condition all together ) if values are same you want to move to pointer for both nodes to next one and also add both values to the third list generated.. -> that way it might give more accurate results.
@@SraddhanjaliAcharyatilaprimera - correct .. else clause does not have condition specified so it will handle all clauses.. and we dont need to move both the pointer in forward direction since we need all the values in final array ! thanks for pointing that out !
![อยู่คนเดียวกับเขา - ส้ม มารี (Zom Marie) [Official MV]](http://i.ytimg.com/vi/gq1cWAIQDLg/mqdefault.jpg)
![[TH] 2024 PMSL SEA W2D3 | Fall | ถ้าเล่นไม่ดี ไปแก้ตัววันเสาร์](http://i.ytimg.com/vi/CTmci32hvP8/mqdefault.jpg)
they got me with the term splicing them together I didn't know I could have made a new list
bro same here, i was out here with a million pointers trying to merge them into one lmao
@Kevin
Thanks for making this video.
Just a quick thing to point the time complexity in the worst case will be O(M+N) as we may have to iterate all the values in both the lists, this happens when the values in the lists are of same range.
Yea I was just about to mention that. I think the test data on this question is fairly weak imo
At the end that will still be O(N)
Got this question on a Facebook interview, happy to see I used the same approach as you!
Did you get it?!
Did they mention the recursive approach or nah?
@@drywater3729 I chose an offer from the Bank of England instead
@@bosteador Yeah they don't mention it explicitly - they just sort of let you do your own thing and ask you questions as to why you're doing what you're doing and how you could improve it etc.
You got asked an easy question at facebook? Although leetcode has some 'hard' easy problems, I was expecting much more advanced/sophisticated than this question
Alternatively you can start with an empty list and conditionally make your first node the head.
I found it tougher if you cannot create a new list but merge the two in place and return only one of the lists. I saw that in an interview too.
Your explanations are awesome. Thanks for the video man!! Love from India. :D
Anytime Suryansh and thank YOU for the support!!! :)
The explanations are really good. Thanks!!
@Kevin, Really like your coding walk through style! Could you please add to your list some of Leetcode problems: Longest Palindrome Substring(#5), Minimum Window Subsequence(#727), Minimum Window Substring(#76), Longest continuous increasing subsequence(#674). I know its a huge list but would really like to see your thought process :) BTW, problem explanation is so good. Thanks!
Do you get compliments on your eyes? They're nice. I had to share, what use is it keeping it to myself
Keep up the good work. You make it look so easy.
IPhone Apple thanks! And these questions are hard don't be fooled!!! It takes a lot of practice!
Hi ! My question is only about this last part :
if(l1!=null){
dummy.next=l1;
}
if(l2!=null){
dummy.next=l2;
}
Doesn't this block of code logically take care of the numbers which haven't been added in the while loop ?
For example our lists are : list1=[1,2,4] list2=[1,3,4,7,8,9]
So the while loop will form the list=[1,1,2,3,4,4] and the rest will be added by the block :
if(l2!=null){
dummy.next=l2;
}
My question is : doesn't that block add only one node ? Because it would be able to add multiple nodes . It would be in my opinon something like this :
while(l2!=null){
dummy.next=l2;
l2=l2.next;
}
What is the logic mistake that I made ? Thank you in advance!
I was not able to do this on my own, i am not sure but it doesn't look that tough but I was still not able to :/. Guilty Feels max lmao
PS: Thanks for the explanation!
seriously, man you nailed it. so helpful
HELL NO. IF AMAZON REALLY ASKED THIS, I WOULD BE THE NEW CEO
Both the time and space complexity will be O(n+m). n represents the number of elements in L1 and m represents the elements in L2. Because we are creating extra space, the space complexity will also be O(n + m)
I believe the time complexity should be O(min(n,m)) whichever list is smallest determines the loop range after that we exit and just set the result node next to the remaining list node
Great video, Kevin! I have a question regarding the runtime analysis though. I think what you described in the video is correct, but the caption is wrong. The runtime complexity should be O(M+N) in the worst case, where M, N are the lengths of the two list. If the two lists have smaller values alternatively (e.g. one is 1->3->5->7, while the other one is 2->4->6->8), then you have to iterate through both lists.
Thanks mate, i was so confused on the Time complexity of this problem. you made it clear!!
You give the best explanations! Thank you so much!
Anytime!!! :)
if these ListNodes were pointers and we created dummy = new ListNode(-1); then would it make sense to delete that dummy node from memory before returning head->next?
thanks so much! I couldn't understand the solutions on leetcode, but this made it click
Hey Kevin, I like the way you explain your approach and then how you convert that in code. Great
nishant singh thanks Nishant! If you like my explanations be sure to join the interviewing service I created thedailybyte.dev/?ref=kevin I recommend joining a premium plan if you can!
@@KevinNaughtonJr Yeah...sure...will have a look
Why sometimes there are lists left? If the while uses && shouldn't stop only when both are null?
I really enjoy watching videos to get more knowledge on coding.
Bro your videos are fire, so helpful, thank you so much
Dumb question, but which part of the code takes care of that case where l1 = l2?
great video bro! thank you for taking the time to explain the logic behind ur algorithm
Your videos are really helpful !! Thank you Kevin....keep doing 😋
Thanks Pooja and don't worry I will :)
This is a great video! Thanks. How do you know to set it equal to null?
Thanks for the video! It's very useful to hear your explanations during the problem
Anytime Oliver and thanks!
Hi. I know about reference types (in Java or C#) but I don't understand how `dummy` get its value. what topics should I read about to know how its works?
Hi Kevin! Love your channel
Anytime Prabhnoor, thanks for the support. I'll put that one on my list :)
Hi Kevin! Great videos! Thank you so much for your explanations.
I'm a bit confused though. So on line 15 and line 18 when you do : dummy.next =l1 (and l2 respectively), does it not append everything left in list L1 or L2 to the dummy list (just as it would in line 25 and 27 respectively?)
I have the same doubt. I think to add all remaining elements in l1 or l2, we will have to use one more while loop. It would be great if Kevin clarifies it.
Hello, L1 isn't a value, it is a node. A node has references to each other item in the list. At the beginning when we loop through and put items in individually, that happens because we splice in other nodes after them which changes the references. At the end, where we just put in either L1 or L2, the references remain intact, so all the remaining values get put into the list as well. Hope that helps!
Did you ever find a good explanation to this?
Any of you guys know why the need to put next to dummy.next for the first value instead of just putting dummy? I am really confused. :((
I didn't get why is && statement used in the loop instead of || ,is it necessary for both the lists to get null
What'sthe point of head variable? can't we just return dummy.next at the end
Hey Kevin!! Big Fan of your videos and you've helped me a lot while preparing for my interviews, can you please make a video on 'Reverse Nodes in k-Group' Leetcode problem?
Hi Kevin. Great video. I love how you explain these problems. I do have one question though. I am a second year CS student who just learned about linked lists. In my class we created a new node object every time we added to our linked list. So for example, if we had 5 items in our linked list there would be 5 objects each pointing to the previous object in the list. It seems like in your code you are just changing the values in your dummy list without creating new objects. I was wondering if you could explain how the dummy list is being appended in your code without creating new objects?
It's been almost a year so I'm sure you understand this now but in case anyone else had the same question:
Your teacher created multiple new Nodes because he was starting from scratch. In this case we are given Nodes to work with.
So if we work with the same scenario that Kevin has in this video, if have two ListNodes being passed into our function. These two ListNodes can look something like:
l1 = 1 -> 2 -> 3
l2 = 1 -> 3 -> 4
Keep in mind that although we are just showing numbers here you should really think of the numbers encased in a 'ListNode' object.
When we create a new dummy ListNode in our code:
ListNode dummy = new ListNode(-1), we now have something that looks like this:
-1 -> null
Now our next variable in our ListNode class holds a ListNode object. So if you want to assign a value to our next variable you can do something like
l1.next = new ListNode(5) (We're creating a new ListNode object and assigning our next variable to it)
However we also have our other ListNodes, l1, and l2, these are ListNode objects that have already been instantiated (created).
So we know our next variable holds ListNode objects and l1 which currently holds the value 1 is a ListNode object so we can just go
dummy.next = l1; (since l1 is a ListNode object)
So now dummy looks like
-1 -> 1 -> 2 -> 3
@@PureForloko Thanks this is super helpful! I am also confused by this but you answer all the questions I have.
@@Sunshine-mj2pf glad to hear it man!
how do i get the the length of the listnode l1 for example?
I would have preferred if you wouldnt change the original node and practice immutability
ty bro
Awesome, nice explanation! Ty
Thanks
what happens if have one valid list and the other is a null pointer ? how does dummy node help in this case ??
Can't we use the solution you have mentioned in K sorted lists that use min-heap?
Your approach is correct but I guess in the final if-else block where we check if there are any more elements left in either of the two lists, there we need to use while loop inside our if / else block to check how many more elements are still left either in list1 or list2 after one of the list reaches to null in our upper while loop.
And we also need to move dummy = dummy.next in the bottom if-else block along with the l1 = l1.next || l2 = l2.next
That's the same thing I just asked about .
Here was my comment :
Hi ! My question is only about this last part :
if(l1!=null){
dummy.next=l1;
}
if(l2!=null){
dummy.next=l2;
}
Doesn't this block of code logically take care of the numbers which haven't been added in the while loop ?
For example our lists are : list1=[1,2,4] list2=[1,3,4,7,8,9]
So the while loop will form the list=[1,1,2,3,4,4] and the rest will be added by the block :
if(l2!=null){
dummy.next=l2;
}
My question is : doesn't that block add only one node ? Because it would be able to add multiple nodes . It would be in my opinon something like this :
while(l2!=null){
dummy.next=l2;
l2=l2.next;
}
What is the logic mistake that I made ? Thank you in advance!
Best explanation out there.
You should do a Kevin Naughton x CS Dojo collab
Haha I'd love to that'd be so cool!!!
Plus one! Thanks a lot for the videos Kevin! :)
Why is he returning head.next? What is head.next pointing to?
Wait, this solution also modifies the order of the l1 and l2 to become the merged list
Thank you kevin.
6:10 6.10 while is this an if and not a while?
I'm confused by that as well
You only need to append the one node, because the one node references the remaining nodes.
I just got asked this in an interview
how did it go?
@@unknownman1 I had never seen this problem, but luckily my interviewer was nice and guided me to the right answer.
missing return statement or is it just me ? it should return dummy.next, correct?
rather, it should return head.next ?
@@anyadavidovich1083 Yep, he got that at 7:53
So helpful!
Thanks Court!
Thanks Kevin!
Anytime Thomas, thanks for the support!
Who the fuck gave one dislike?
I don't know why people are so mean?
BTW, nice video Sir.
bro please make a video for this problem.
138. Copy List with Random Pointer
You're awesome!
i don't understand how head.next is not null? When was head.next ever assigned to?
Bro
Can u provide source code link
Easier solution:
if (head1.data < head2.data) {
head1.next = mergeSortMethod(head1.next, head2);
return head1;
} else {
head2.next = mergeSortMethod(head1, head2.next);
return head2;
}
Can you elaborate what mergesortmethod(head1.Next,head2) is doing? Like i put two nodes as arguments and recieving one node, but which one?
why return head.next
You have used && , so it comes out only if both the condition is false but the if condition will be false because when we are out of the while loop both the l1 and l2 will be null, I guess you should have used || condition
You can also do or operation, but suppose the smaller list got exhausted in while loop, then you can simply append the remaining big list in single operation to improve performance. Never doubt Kevin naughton
What if l1.val == l2.val, it seems you are only checking less than or greater than
Exactly my question. I believe need to add - elseif (and thereby third condition all together ) if values are same you want to move to pointer for both nodes to next one and also add both values to the third list generated.. -> that way it might give more accurate results.
@@nidhidesai3502 I think the equality part is handled by the else clause as well as for greater than check.
@@SraddhanjaliAcharyatilaprimera - correct .. else clause does not have condition specified so it will handle all clauses.. and we dont need to move both the pointer in forward direction since we need all the values in final array ! thanks for pointing that out !
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1==NULL) return l2;
if(l2==NULL) return l1;
ListNode* dummy;
if(l1->valval){
dummy=l1;
dummy->next=mergeTwoLists(l1->next,l2);
}
else{
dummy=l2;
dummy->next=mergeTwoLists(l1,l2->next);
}
return dummy;
}
Thx for another great video kevin. Written explanation here: medium.com/@7anac/coding-interview-question-merge-two-sorted-lists-leetcode-21-fb2b166b5
vvv
what an idiotic video.. started explaining the content way to late and no visuals to go thru.. downvoting