- Time Complexity: O(n+m) n = no of nodes in list1 m = no of nodes in list2 - Memory Complexity: O(1) - We have a constant space, since we are just shifting the pointers
@@Donquixote-Rosinante There's no array been created. Note that the nodes are likely in different locations in memory & are just pointing to each other. What this solution is doing is changing what existing node is pointing to.
I had a hard time understanding the dummy..next thing, but finally, I did. Here is my explanation. Think of the nodes (ListNode) as if each of those was stored in a different memory slot, so each slot has a "next" and a "val" value. So, basically, when you do: tail = dummy ---> you're creating a tail pointer or reference to where the dummy object is. then when you do: tail.next = list1 ----> you're updating the "next" value in the memory slot where the tail is pointing, which is exactly the same slot where dummy is pointing. then later you do: tail = tail.next ---> At this point, tail.next is already list1, so you're telling tail to point to the memory slot where list1 is; so if you update later the "next" value of list1, you won't be updating the dummy anymore since tail and dummy are now pointing to different memory slots. I had to open a Python editor and run the following code to really understand what was happening. id() is a fn that returns a unique memory identifier for the object. class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next node1 = ListNode(val=0, next=None) node2 = node1 print('node1 val', node1.val) print('node1 next', node1.next) print(id(node1), id(node2)) print("*****") node3 = ListNode(val=3, next=None) print('node1 val', node1.val) print('node1 next', node1.next) print(id(node1), id(node2)) print("*****") node2.next = node3 node2 = node3 print('node1 val', node1.val) print('node1 next', node1.next.val) print(id(node1), id(node2)) print("*****")
Thank you! Came to the comments for this. I was pretty confused by that move as well. LinkedLists are super weird. I always get confused if node.next.next is getting the next node object or setting the next node's next node property. I guess it's just by context...
Just watched your video on linked lists in your DSA course. That video alone was worth the price. I've been racking my brain ever since.I first learned about linked lists, and your video is the first time it made sense to me. Thank you.
1. by assigning tail = assignment now we made tail a node list (linked list: having value and pointer ) 2. we are using tail to connect the linked list and updating its value , so in last iteration it stores only the value of last node 3. now the node are properly connected and we know the beginning of node that is dummy 4. we return dummy . next because thats where the first node is basically we use tail to connect nodes in proper order and dummy to remember the first node
i guess it tail is pointing to the same memory location as that of head and tail.next to head.next so change in head.next is same to tail.Please correct me if im wrong!
Linked list contain head and tail, when create the dummy node tail is pointed to dummyNode(Cause it is the last node of Dummy List, when every time new node is added tail is updated to last node(tail = tail.next))
I don't understand why/how the dummy variable is dynamically updating. Why doesn't it remain 0? And why doesn't it also shrink when you're tail = tail.nexting?
In Python, x = y = ListNode() creates a single instance of ListNode() and assigns references to both x and y. Both variables point to the same object in memory. Changes made via x will be reflected in y, and vice versa.@@jeffreysneezos
after creating dummy = ListNode() there is an object in memory (lets call it obj1), which contains int val and ListNode next in itself. "dummy" in this case is not an object, but a reference/link to this object in memory ("dummy" -> obj1) when we write tail = dummy, we are not creating new object ListNode, but only copying link to obj1, so we get "tail" -> obj1 after that we do not touch "dummy", so it always pointed at obj1 to work with obj1 we use "tale" reference when we write tale.val - we accessing obj1.val when we write tale.next - we accessing obj1.next if we write tale.next = ListNode() - now obj1.next contains reference to new object in memory (lets call it obj2) after that if we write tale = tale.next - it means that we are changing reference, that our "tale" contains and now it's "tail"->obj2 dummy object (obj1) was created just for our comfort, so we shouldn't figure out how to create first object in cycle after all work done we don't need it anymore, so we do dummy = dummy.next (so now it's "dummy"->obj2) return dummy I believe you figured it out already, so I hope my reply will help someone else
because the initiliazed ListNode head has default value of 0 and we dont want that to be the head of our returned ListNode, because this head is used just to initialize it
After smashing my head for hours, I understood it now and thought of writing it down so others and my future self can understand. A linked list here can be represented like this -> linkedList{VAL,NEXT=linkedList{VAL2,NEXT=linkedList{VAL3,NEXT=..............}} Once you visualize this you will get a better understanding as how this is actually maintained. Now coming to the DUMMY part. We are creating it like this -> linkedList{0,NEXT=None} now consider this as an OBJECT called obj1 We also referenced it in the TAIL or CUR, so TAIL or CUR is also obj1 Now the WHILE loop will run till it hits NEXT=NONE of one of the lists(l1 or l2) Now this is where all the action will happen if l1's 1st node is smaller or equal we will update CUR.NEXT = l1 so now CUR or OBJECT obj1's next is pointing to l1 which lets say is OBJECT obj2-> so we just added the whole l1 in the NEXT of CUR -> linkedList{0,NEXT=l1(visualize how the linkedList looks here)} next step is CUR = CUR.NEXT here what we are doing is changing the reference that CUR was following till now which was obj1 to basically l1(as CUR.NEXT has l1) lets say obj2 The DUMMY is still pointing to obj1 which in turn is pointing to obj2 We will continue this trend and one thing will point to another with the help of CUR while DUMMY will stay at the HEAD obj1 which will be pointing to obj2->obj3->.... visualize the linkedList again Once one of the 2 list's NEXT hits NONE we will come out of WHILE loop and simply add the other list in the NEXT of the CUR linkedList{VAL,NEXT=linkedList{VAL2,NEXT=linkedList{VAL3,NEXT=(Remaining l1 or l2}} now our final DUMMY will look like this linkedList{0,NEXT=linkedList{VAL,NEXT=linkedList{VAL2,NEXT=linkedList{VAL3,NEXT=(Remaining l1 or l2}}} SO we will simply return the NEXT of the DUMMY linkedList{VAL,NEXT=linkedList{VAL2,NEXT=linkedList{VAL3,NEXT=(Remaining l1 or l2}}} I hope this clarifies it for you.
Originally I misunderstood the question and thought you need to merge list 2 into list 1, without creating a new list (not allowed to create a new node). Was very confused how to do that correctly...
I had a hard time with this problem because I didn't think of using a dummy node and returning dummy.next, therefore I spent time merging list2 into list1. I was not happy with that solution so I wrote it again using a stack and that was a lot cleaner. I knew there had to be a smaller code solution which this video presents.
Dummy.next will be the first node in the merged list, while tail.next would be the last node. Since we want to return the head of the new list, we return dummy.next.
@@didoma73 this is because he's using Python and everything is considered an object here. When he did tail = dummy, he stored the reference(pointer) for dummy variable into tail. Now every time the tail variable is changed, it'd also affect the dummy variable
@@OM-el6oyhe is making tail point to dummy,, initially dummy is head node. Starting from the head node, tail keeps getting updated i.e new node will be appended.
@@frankl1 I'm not sure how things work in python, but each time we assign value to tail . next, doesn't it mean we use sizeof(ListNode()) memory space ??? meaning memory usage is still O( |L1| + |L2| ) ??????
@@primogem_160 Oh my bad, you are right. The first assignment to tail.next changes its value from None (basically NULL in C and C++) to the reference to a ListNode object and subsequent assignments do not increase the memory space. Both solutions are O(1) memory as no new linked list is created, only the next attributes of each node are updated + the space for the dummy node if it is used. Do you agree?
Can you explain at what moment dummy.next is assigned to tail? if I do it explicitly like this dummy = ListNode() tail =ListNode() dummy.next = tail then I need to return this for all to work return dummy.next.next 🥲what's going on?
You have created, two empty nodes (dummy and tail ). When you are updating new tail (tail.next), new tail is always pointed to to last node; two return head of new list you have to return (dummy.next.next) {dummy itself is empty dummy.next(your code) also empty, your actual new list start with dummy.next.next(head) onwards}
Wait, where is ListNode taken from, lol. In my IDE it says it is an unresolved refference. Wth is going on.. and how is ListNode connected to the -1 of l1??
hey @NeetCode , do a background video. im sure youre a god judging by your natural ability to explain it simply. Ive worked in CV and SW for years, and ive never used a linked list for any purpose \o/ Also, can you explain why the return is dummy.next and not just dummy? thanks
since 4 in list 2 was remaining we have to do a conditional statement if list1: current.next = list1 if list2: current.next = list2 this statement only holds true because of the 4 was only remaining node in list2 it has nothing to do with 4->5->6 nothing in the question didn't ask for additional nodes
consider dummy as the head and tail as a temp variable you are using to iterate through so in the end dummy remains the same as head but tail keeps moving forward so we return dummy.next since dummy.next is the first node that was inserted from either of the lists.
@@vansh9857Yh but dummy.next was never inserted. We are confused because it’s basically saying that what has been done to tail has also been done to dummy enabling us to get the answer as dummy.next as that is not the case
@@dnm9931 that also my question. dummy has 0 value by default and re-assign to tail which also now has 0 value. basically they share same instance of ListNode()/same value. i understand the rest except this dummy and tail which pointing the same to ListNode().
Hi, I am new to programming, why are we returning dummy here as we are not appending anything to dummy and why are we not returning tail, can anybody please help to overcome this confusion?
you can't return tail because it's not linked to anything after. but you return the dummy since you assigned it to the tail, so you keep track of the tail in that way while having the dummy node at the same time.
dummy is the FIRST node. Tail is used as a Reference node which moves from dummy to all the other nodes(in order to point to the next one). in other words, since Linked list works needs a starting node to be able to point to the next, we create Dummy which is supposed to be fixed at beginning and cant be used for traversal.
So when looking on Leetcode it doesn't automatically input the changes you made to the l1: ListNode etc. It would be really nice to explain why you chnaged it because it throws you off if your not aware as leetcode doesn't have those changes
i am wondering why we only need an if condition for the rest of l1 or l2, I used a while because I thought there could be more than one element in one of the list
@@adamrao6161 Could you further explain how you reason this part please? I still don't understand why it will store all the list value without using a loop. Thank you!
@@HsiaoyuanA92 at this point you have two lists, such as. 1->2->3 and 4->5->...X You only need one connection from 3 to 4 to join the two lists together.
Hi someone previous asked a question I am dying to know! "in the end, dummy.next returns the entire linkedlist, because people say that each node recursively goes to each following node since they all have pointers. So this leads me to have a question. lets say for example that we are on the first iteration of the while loop and l1.val < l2.val, so the 'if' statement will fire. as a result, we are setting tail.next to list1. am i correct in thinking that tail will now be equal to the entire first linked list? or in other words, tail=[1,2,4], for this brief current moment until the next iteration of the while loop? And then on the next iteration it will be overwritten as the while loop continues on until the end where it will be fully correctly merged. Kinda confused by this! Thanks"
Linked lists are represented with their heads, so list1 is actually head1 and list2 is head2. We can reach the whole linked list from the head, so at first we really are connecting the whole list1 to the tail, like you said. However it doesn't have any significance since in the next loop the next pointer of the tail, which for that moment makes the whole list1 reachable, will be seperated from the rest of the list1 and will be connected to the next node from either list1 or list2. Again we'd able able to reach the remaining part of the added node's list at that moment, until the tail's next pointer is connected to a new node. This would continue like that until the end of the 2 lists, so in the end the tail's next pointer would point to null and we'd get a list containing the nodes from both lists.
because dummy points to the HEAD, or the beginning, of the linked list. the head represents the entire linked list because that's all you need to traverse the entire linked list. from the head you go to the next node, and from that node you go to the next node, and so on until you reach the end. if you return the TAIL, you're returning the end of the list... which is useless because you can't traverse backwards for this type of linked list.
I don’t understand the point of dummy and why it helps in edge cases, also won’t this list have just an empty node in the dummy node which increases the size of the list?
in the end, dummy.next returns the entire linkedlist, because people say that each node recursively goes to each following node since they all have pointers. So this leads me to have a question. lets say for example that we are on the first iteration of the while loop and l1.val < l2.val, so the 'if' statement will fire. as a result, we are setting tail.next to list1. am i correct in thinking that tail will now be equal to the entire first linked list? or in other words, tail=[1,2,4], for this brief current moment until the next iteration of the while loop? And then on the next iteration it will be overwritten as the while loop continues on until the end where it will be fully correctly merged. Kinda confused by this! Thanks
because dummy.next references another node on the linked list. This node also has a next pointer, as does the following, so on and so on. Its a recursive data structure
Because the "tail" gets advanced while either list is non-null. You could return tail after moving back to the start of the list, but dummy.next is much easier.
After comparison list1.val and list2.val at first time, updating list(ex. list1 = list1.next) means that linked list started from 2nd node entered list1 ? is not 2nd node entered to list1?
Can you plz tell me what is the meaning of below 4 lines and how they are working when any one of the two list is completely traversed. If l1: tail.next = l1 elif l2: tail.next = l2 And why we have have to return dummy.next instead of dummy Thanks ❤️
@@kashifahmed_1995 1. Because the while loop exits when one of the lists become null, so we append the rest of the list which is not null to the end of our result list. 2. Because we start appending from dummy.next, the head of dummy is just a dummy so we can avoid the edge case of the list being empty.
pulling my hair because of this why does the following for the while loop part not work? why do i need the else statement? while list1 and list2: if list1.val > list2.val: print(list2.val) tail.next = list2 list2 = list2.next if list1.val
Hi, just asking for clarification: I understand when we initialize dummy, it starts with a node of value 0, as per the __init__() dunder method. So when we return dummy.next, we ignore the initial node, since that's not part of either l1 or l2. But doesn't .next typically refer to the "next node in the linked list", as opposed a "list of nodes where the head is discarded"? Rather, if you don't assign dummy = dummy.next for example, is that what I should expect? So dummy.next.next would return a Linked List object, with the head and the node that the head is pointed to removed? Finally, would a more intuitive implementation be having set the init self.val = None, and then returning dummy, not dummy.next? I am self teaching myself DSA and programming in general, so apologies if my question sounds incoherent.
I think the space should be O(1) because we are only making the new dummy node and connecting the already existing nodes. The input size wouldn't change how much extra space we need for the function.
There's something that's confusing me. What if one list is null and the other still has multiple nodes remaining? Wouldn't the second half of the code need to be inside another while loop? Otherwise, isn't your code just adding 1 of the remaining nodes onto the merged list and leaving however many were left floating?
Each node has a next property which points to the next node, so by adding just the next node of the remaining list, you 'automatically' add the rest of that list since that node that you added points to the next one, which points to the next one, etc.
i just got it myself. the nodes each point to the same literal data. so when you make dummy it points to the same thing as tail, as you change tail dummy still points to everything tail points to because dummy is the first node and points to the second (where tail starts creating nodes). this is the harshest wake up call that your variables do not store your data they just point to it SMH
Can someone tell me why this is wrong? Trying to understand how linked lists work.. class Solution(object): def mergeTwoLists(self, list1, list2): dummy = ListNode() f = dummy while list1 and list2: if list1.val < list2.val: f = list1 list1 = list1.next else: f = list2 list2 = list2.next f = f.next if list1: f = list1 elif list2: f = list2
dummy is the FIRST node. Tail is used as a Reference node which moves from dummy to all the other nodes(in order to point to the next one). in other words, since Linked list works needs a starting node to be able to point to the next, we create Dummy which is supposed to be fixed at beginning and cant be used for traversal.
bro this is my code: class Solution(object): def mergeTwoLists(self, lists1, lists2): dummy = ListNode() tail = dummy while lists1 and lists2: if lists1.val < lists2.val: tail.next = lists1 lists1 = tail.next else: tail.next = lists2 lists2 = tail.next tail = tail.next break if lists1: tail.next = lists1 elif lists2: tail.next = lists2 return dummy.next it's not giving me the correct answer, the output I got is [1,1,2,4] here only my first list is working but not the second can you help me, please.
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
could we use recursion to solve this problem. maybe it would run faster then iterating. Don'nt know about this give your opinion on this
this was probably the first leetcode problem where i knew what i had to do and my original code was pretty close to the solution. Im proud of myself
Super bro . But how I too was learning but this is too difficult
But u still got it wrong 😂
@@sparrow2068 Laughing at others' efforts. Heartless boy.
im sorry@@Humon66
@@sparrow2068 hope with that you feel better
- Time Complexity: O(n+m)
n = no of nodes in list1
m = no of nodes in list2
- Memory Complexity: O(1)
- We have a constant space, since we are just shifting the pointers
it is O(n+m) space complexity, there is literally new list created
@@jey_n_code It is not, the only new thing you've created is the dummy node. The new list is made up of the nodes that already existed from the input.
@@KCIsMehow the dummy node is O(1) and array = [] is O(n) that's weird???
Wouldnt memory be O(max(n,m)) since the call stack can have up to max(n,m) recursive calls * O(1) operations each?
@@Donquixote-Rosinante There's no array been created. Note that the nodes are likely in different locations in memory & are just pointing to each other. What this solution is doing is changing what existing node is pointing to.
I had a hard time understanding the dummy..next thing, but finally, I did. Here is my explanation.
Think of the nodes (ListNode) as if each of those was stored in a different memory slot, so each slot has a "next" and a "val" value. So, basically, when you do:
tail = dummy ---> you're creating a tail pointer or reference to where the dummy object is.
then when you do:
tail.next = list1 ----> you're updating the "next" value in the memory slot where the tail is pointing, which is exactly the same slot where dummy is pointing.
then later you do:
tail = tail.next ---> At this point, tail.next is already list1, so you're telling tail to point to the memory slot where list1 is; so if you update later the "next" value of list1, you won't be updating the dummy anymore since tail and dummy are now pointing to different memory slots.
I had to open a Python editor and run the following code to really understand what was happening. id() is a fn that returns a unique memory identifier for the object.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
node1 = ListNode(val=0, next=None)
node2 = node1
print('node1 val', node1.val)
print('node1 next', node1.next)
print(id(node1), id(node2))
print("*****")
node3 = ListNode(val=3, next=None)
print('node1 val', node1.val)
print('node1 next', node1.next)
print(id(node1), id(node2))
print("*****")
node2.next = node3
node2 = node3
print('node1 val', node1.val)
print('node1 next', node1.next.val)
print(id(node1), id(node2))
print("*****")
Thank you! Came to the comments for this. I was pretty confused by that move as well. LinkedLists are super weird. I always get confused if node.next.next is getting the next node object or setting the next node's next node property. I guess it's just by context...
Thank you, I know this was considered an easy problem but it was difficult for me to fully grasp the linked list concept. This video did wonders
I found LinkedList really confusing in python, mainly because I can't visualize it while coding.
@@varunshrivastava2706 me too
@@willowsongbird didnt ask. ruth.
@@varunshrivastava2706 I'm still very confused about this whole dummy list thing.
@@varunshrivastava2706 do you have any python recommendatios for same?
This channel is so underrated.
fr
Just watched your video on linked lists in your DSA course. That video alone was worth the price. I've been racking my brain ever since.I first learned about linked lists, and your video is the first time it made sense to me. Thank you.
Good explanation. This is similar merging technique done in the merging part of merge sort
Exactly.
Done thanks
Todo:- implementation copy to notes
Again using the dummy head technique to avoid edge cases similar to delete node
Hmm, I'm having trouble understanding what exactly is happening with the tail = dummy assignment? Is that like making a copy of the node or?
Tail starts from the dummy node, thats why tail is assigned to dummy.
1. by assigning tail = assignment now we made tail a node list (linked list: having value and pointer )
2. we are using tail to connect the linked list and updating its value , so in last iteration it stores only the value of last node
3. now the node are properly connected and we know the beginning of node that is dummy
4. we return dummy . next because thats where the first node is
basically we use tail to connect nodes in proper order and dummy to remember the first node
i guess it tail is pointing to the same memory location as that of head and tail.next to head.next so change in head.next
is same to tail.Please correct me if im wrong!
Linked list contain head and tail, when create the dummy node tail is pointed to dummyNode(Cause it is the last node of Dummy List, when every time new node is added tail is updated to last node(tail = tail.next))
@@varunnarayanan781 yes that’s correct
Bruh, I did this problem without making a new list. I knew it seemed too hard for an easy,
Same thing happened to me bro :(
I spent almost 2 hrs on this.
@@aniketsrivastava7968 Linked lists are tough!! I guess now you have become comparatively good at it. Since you saw this video 3 months ago?
I don't understand why/how the dummy variable is dynamically updating. Why doesn't it remain 0? And why doesn't it also shrink when you're tail = tail.nexting?
Hey @trivialnonsense, did you end up finding this out? I'm stuck on the same thing...
does anyone know ?
In Python, x = y = ListNode() creates a single instance of ListNode() and assigns references to both x and y. Both variables point to the same object in memory. Changes made via x will be reflected in y, and vice versa.@@jeffreysneezos
after creating dummy = ListNode() there is an object in memory (lets call it obj1), which contains int val and ListNode next in itself.
"dummy" in this case is not an object, but a reference/link to this object in memory ("dummy" -> obj1)
when we write tail = dummy, we are not creating new object ListNode, but only copying link to obj1, so we get "tail" -> obj1
after that we do not touch "dummy", so it always pointed at obj1
to work with obj1 we use "tale" reference
when we write tale.val - we accessing obj1.val
when we write tale.next - we accessing obj1.next
if we write tale.next = ListNode() - now obj1.next contains reference to new object in memory (lets call it obj2)
after that if we write tale = tale.next - it means that we are changing reference, that our "tale" contains and now it's "tail"->obj2
dummy object (obj1) was created just for our comfort, so we shouldn't figure out how to create first object in cycle
after all work done we don't need it anymore, so we do
dummy = dummy.next (so now it's "dummy"->obj2)
return dummy
I believe you figured it out already, so I hope my reply will help someone else
Your reply help me, thank you!@@mio1201
this is the new updated solution:
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode()
tail = dummy
while list1 and list2:
if list1.val < list2.val:
tail.next = list1
list1 = list1.next
else:
tail.next = list2
list2 = list2.next
tail = tail.next
if list1:
tail.next = list1
elif list2:
tail.next = list2
return dummy.next
How would we do this without creating a new linked list?
Why are we returning dummy.next while the value for dummy is not update after it initialise(line 8)?
still do understand that at all
because the initiliazed ListNode head has default value of 0 and we dont want that to be the head of our returned ListNode, because this head is used just to initialize it
After smashing my head for hours, I understood it now and thought of writing it down so others and my future self can understand.
A linked list here can be represented like this -> linkedList{VAL,NEXT=linkedList{VAL2,NEXT=linkedList{VAL3,NEXT=..............}}
Once you visualize this you will get a better understanding as how this is actually maintained.
Now coming to the DUMMY part. We are creating it like this -> linkedList{0,NEXT=None} now consider this as an OBJECT called obj1
We also referenced it in the TAIL or CUR, so TAIL or CUR is also obj1
Now the WHILE loop will run till it hits NEXT=NONE of one of the lists(l1 or l2)
Now this is where all the action will happen
if l1's 1st node is smaller or equal we will update CUR.NEXT = l1 so now CUR or OBJECT obj1's next is pointing to l1 which lets say is OBJECT obj2-> so we just added the whole l1 in the NEXT of CUR -> linkedList{0,NEXT=l1(visualize how the linkedList looks here)}
next step is CUR = CUR.NEXT here what we are doing is changing the reference that CUR was following till now which was obj1 to basically l1(as CUR.NEXT has l1) lets say obj2
The DUMMY is still pointing to obj1 which in turn is pointing to obj2
We will continue this trend and one thing will point to another with the help of CUR while DUMMY will stay at the HEAD obj1 which will be pointing to obj2->obj3->.... visualize the linkedList again
Once one of the 2 list's NEXT hits NONE we will come out of WHILE loop and simply add the other list in the NEXT of the CUR
linkedList{VAL,NEXT=linkedList{VAL2,NEXT=linkedList{VAL3,NEXT=(Remaining l1 or l2}}
now our final DUMMY will look like this
linkedList{0,NEXT=linkedList{VAL,NEXT=linkedList{VAL2,NEXT=linkedList{VAL3,NEXT=(Remaining l1 or l2}}}
SO we will simply return the NEXT of the DUMMY linkedList{VAL,NEXT=linkedList{VAL2,NEXT=linkedList{VAL3,NEXT=(Remaining l1 or l2}}}
I hope this clarifies it for you.
Thanks a lot!!! finally understood how it works🫡
Originally I misunderstood the question and thought you need to merge list 2 into list 1, without creating a new list (not allowed to create a new node). Was very confused how to do that correctly...
dude me too! I was kinda just beating my head against the wall trying ti figure out how to do that. Best of luck to you friend!
Same to you. We'll get there eventually!
Such a useful source of learning. Well done.
Thank you very much for sharing 🌷
I had a hard time with this problem because I didn't think of using a dummy node and returning dummy.next, therefore I spent time merging list2 into list1. I was not happy with that solution so I wrote it again using a stack and that was a lot cleaner. I knew there had to be a smaller code solution which this video presents.
Can you clarify why you return dummy.next instead of tail or tail.next? Thanks in advance
Dummy.next will be the first node in the merged list, while tail.next would be the last node. Since we want to return the head of the new list, we return dummy.next.
@@NeetCode But when was dummy.next ever assigned to?
@@didoma73 this is because he's using Python and everything is considered an object here. When he did tail = dummy, he stored the reference(pointer) for dummy variable into tail. Now every time the tail variable is changed, it'd also affect the dummy variable
@@guiningotoshuki3845 so when he did tail = dummy, he made dummy point to tail?
@@OM-el6oyhe is making tail point to dummy,, initially dummy is head node. Starting from the head node, tail keeps getting updated i.e new node will be appended.
What is the naming reason behind "tail"? I've seen cur being used often but never tail before - it shouldn't matter but I'm just curious!
tail = last node
It's by convention. Have seen it in many data structure tutorials and books.
Seems common across languages - Python, Kotlin, Java.
You made it so easy . WOW man. Thanks
The part between line 20 to 23 can be simplified to tail.next = l1 or l2.
does it work on c++?
*Here's My Solution using recursion to avoid dummy variable* :-
class Solution:
def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
return mergeTwoLists(l1, l2)
def mergeTwoLists(self, l1, l2):
if l1 == None: return l2
if l2 == None: return l1
if l1.val = l2.val:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
Nice solution. Avoids dummy node, but doesn't this solution use O([l1| + |l2|) memory unlike the solution in the video which uses O(1)?
@@frankl1 I'm not sure how things work in python,
but each time we assign value to tail . next, doesn't it mean we use sizeof(ListNode()) memory space ???
meaning memory usage is still O( |L1| + |L2| ) ??????
@@primogem_160 Oh my bad, you are right. The first assignment to tail.next changes its value from None (basically NULL in C and C++) to the reference to a ListNode object and subsequent assignments do not increase the memory space. Both solutions are O(1) memory as no new linked list is created, only the next attributes of each node are updated + the space for the dummy node if it is used. Do you agree?
@@frankl1 agreed.
I found the approach of using dummy node very clean
why did i ever think inserting from one list into another would be easier, dummy node sure makes thing so damn simple
criminally underrated. thank you
Can you explain at what moment dummy.next is assigned to tail? if I do it explicitly like this
dummy = ListNode()
tail =ListNode()
dummy.next = tail
then I need to return this for all to work
return dummy.next.next
🥲what's going on?
You have created, two empty nodes (dummy and tail ). When you are updating new tail (tail.next), new tail is always pointed to to last node; two return head of new list you have to return (dummy.next.next) {dummy itself is empty dummy.next(your code) also empty, your actual new list start with dummy.next.next(head) onwards}
Wait, where is ListNode taken from, lol. In my IDE it says it is an unresolved refference. Wth is going on.. and how is ListNode connected to the -1 of l1??
this approach is awsome and easy to understand, Thank you Neetcode
hey @NeetCode , do a background video. im sure youre a god judging by your natural ability to explain it simply. Ive worked in CV and SW for years, and ive never used a linked list for any purpose \o/
Also, can you explain why the return is dummy.next and not just dummy? thanks
you're returning dummy.next because when you intialized the list it has an extra node in the beginning called the "dummy" node
i don't even understand why their returning dummy at all, it was never updated or changed since it initialized WTF
@@feijaodoyou find the answer for this? I’m stuck here too
@@dnm9931 I think is because it needs to return the head, the dummy is basically 0 and it assigns to dummy.next, so it points to the head.
Why do we need the code `tail = dummy` at the 2nd line? I'm still confused with it.
Were the lists guaranteed to be the same length? My intuition said to use a while loop vs and if for those final two conditions
since 4 in list 2 was remaining we have to do a conditional statement if list1:
current.next = list1
if list2:
current.next = list2 this statement only holds true because of the 4 was only remaining node in list2 it has nothing to do with 4->5->6 nothing in the question didn't ask for additional nodes
Clear explanation! Thanks.
Hi NeetCode, you videos helped me so much. thank you! do you mind create a video for basic calculator problem on leetcode?
Why are we returning dummy.next ? Isn't dummy equal to empty node. Also we never set dummy.next = tail.
Can somebody please elaborate on tail = dummy? How come returning dummy .next works but not tail .next when we equated them at the start.
consider dummy as the head and tail as a temp variable you are using to iterate through so in the end dummy remains the same as head but tail keeps moving forward so we return dummy.next since dummy.next is the first node that was inserted from either of the lists.
@@vansh9857Yh but dummy.next was never inserted. We are confused because it’s basically saying that what has been done to tail has also been done to dummy enabling us to get the answer as dummy.next as that is not the case
@@dnm9931 that also my question. dummy has 0 value by default and re-assign to tail which also now has 0 value. basically they share same instance of ListNode()/same value. i understand the rest except this dummy and tail which pointing the same to ListNode().
this was kinda helpful, mainly because the concept o f linked lists is new to me
Hi, I am new to programming, why are we returning dummy here as we are not appending anything to dummy and why are we not returning tail, can anybody please help to overcome this confusion?
I am also confused, do you now know the explanation?
you can't return tail because it's not linked to anything after. but you return the dummy since you assigned it to the tail, so you keep track of the tail in that way while having the dummy node at the same time.
Could you explain. why tail = dummy line?
dummy is the FIRST node. Tail is used as a Reference node which moves from dummy to all the other nodes(in order to point to the next one). in other words, since Linked list works needs a starting node to be able to point to the next, we create Dummy which is supposed to be fixed at beginning and cant be used for traversal.
So when looking on Leetcode it doesn't automatically input the changes you made to the l1: ListNode etc. It would be really nice to explain why you chnaged it because it throws you off if your not aware as leetcode doesn't have those changes
i am wondering why we only need an if condition for the rest of l1 or l2, I used a while because I thought there could be more than one element in one of the list
oh wait, i got it.. it's pointed to the rest of the linked list so if there are more elements after it, It still works!
@@adamrao6161 Could you further explain how you reason this part please? I still don't understand why it will store all the list value without using a loop. Thank you!
@@HsiaoyuanA92 at this point you have two lists, such as. 1->2->3 and 4->5->...X
You only need one connection from 3 to 4 to join the two lists together.
congrats on 100k bruh , u deserved it
Hi, thank you for your videos. Which software do you use to make your videos ?
Microsoft Paint 3D
Hi someone previous asked a question I am dying to know!
"in the end, dummy.next returns the entire linkedlist, because people say that each node recursively goes to each following node since they all have pointers. So this leads me to have a question. lets say for example that we are on the first iteration of the while loop and l1.val < l2.val, so the 'if' statement will fire. as a result, we are setting tail.next to list1. am i correct in thinking that tail will now be equal to the entire first linked list? or in other words, tail=[1,2,4], for this brief current moment until the next iteration of the while loop? And then on the next iteration it will be overwritten as the while loop continues on until the end where it will be fully correctly merged. Kinda confused by this! Thanks"
Linked lists are represented with their heads, so list1 is actually head1 and list2 is head2. We can reach the whole linked list from the head, so at first we really are connecting the whole list1 to the tail, like you said. However it doesn't have any significance since in the next loop the next pointer of the tail, which for that moment makes the whole list1 reachable, will be seperated from the rest of the list1 and will be connected to the next node from either list1 or list2. Again we'd able able to reach the remaining part of the added node's list at that moment, until the tail's next pointer is connected to a new node. This would continue like that until the end of the 2 lists, so in the end the tail's next pointer would point to null and we'd get a list containing the nodes from both lists.
Thank you very much
Hey, why do we need to use tail ? Why can't we use directly dummy ?
Then how will you know which one is the first node?
@@farazahmed7 I don't understand...
because dummy points to the HEAD, or the beginning, of the linked list. the head represents the entire linked list because that's all you need to traverse the entire linked list. from the head you go to the next node, and from that node you go to the next node, and so on until you reach the end. if you return the TAIL, you're returning the end of the list... which is useless because you can't traverse backwards for this type of linked list.
The tail can also be called the currentnode which you will be updating
while list1 AND list2, omg, it took me an hour to find this mistake
I don’t understand the point of dummy and why it helps in edge cases, also won’t this list have just an empty node in the dummy node which increases the size of the list?
in the end, dummy.next returns the entire linkedlist, because people say that each node recursively goes to each following node since they all have pointers. So this leads me to have a question. lets say for example that we are on the first iteration of the while loop and l1.val < l2.val, so the 'if' statement will fire. as a result, we are setting tail.next to list1. am i correct in thinking that tail will now be equal to the entire first linked list? or in other words, tail=[1,2,4], for this brief current moment until the next iteration of the while loop? And then on the next iteration it will be overwritten as the while loop continues on until the end where it will be fully correctly merged. Kinda confused by this! Thanks
Hi did you ever figure this out? I'm struggling on the same concept! Thanks!
@@spongbob496 Nah, I still need clarification on this concept haha
I am a bit confused as to why "dummy.next" returns a whole list and not just the next node in line. Can someone explain this to me?
because dummy.next references another node on the linked list. This node also has a next pointer, as does the following, so on and so on. Its a recursive data structure
@@momtheplum185 Thank you. Could you please elaborate. If i use just return dummy, it returning a zero at the begging. Why ?
Can anyone explain why we name dummy as tail ?
I still don't quite get it. The problem description asks us to return the head. The merged linked list is the head?
can someone explain why we need to create dummy? instead tail = ListNode(), is it tail and dummy share of instance of ListNode(). ~confused
Guys this is def not an easy question. Would prob put this medium
I love that dummy technique.
I xopied the same xose .It didnt work
Why am I not able to print(list1.val)?
how do u solve the problem without a dummy node? I'm still kind confused abt the dummy node
Please...!
Can someone clear Why
dummy=tail
return dummy is Correct Ans
But
return tail -> result is [4,4]
Because the "tail" gets advanced while either list is non-null.
You could return tail after moving back to the start of the list, but dummy.next is much easier.
@@si-fi still don't really understand :(. In this time right line we return dummy, tail is [4,4].
@@ngochainguyen91 i still stuck with this, do you understand now? can you explain it to me?
Where do you get the "tail" from in this code? Is that simply a private pointer to the class Node (which is not what we see in this)?
I think tail is a pointer to a node, and in python you don't need to specify the type of the variable
why did you assign dummy to tail?
in short it just helps to keep track of the last node as you add more items to the list.
Where you setting dummyNode.next to tail? how do they directly referenced?
After comparison list1.val and list2.val at first time, updating list(ex. list1 = list1.next) means that linked list started from 2nd node entered list1 ? is not 2nd node entered to list1?
Can someone explain what the listnode is and how it works
after torturing myself to solve this in eclipse using linked list built in methods i am here for the python solution.
# Can some one explain to me why this is the behavior of the code:
while l1 and l2:
if l1.val
Thank you for the neat explanation
Can you plz tell me what is the meaning of below 4 lines
and how they are working when any one of the two list is completely traversed.
If l1:
tail.next = l1
elif l2:
tail.next = l2
And why we have have to return dummy.next instead of dummy
Thanks ❤️
@@kashifahmed_1995 1. Because the while loop exits when one of the lists become null, so we append the rest of the list which is not null to the end of our result list.
2. Because we start appending from dummy.next, the head of dummy is just a dummy so we can avoid the edge case of the list being empty.
why can't the tail value be the dummy?
why cant we just merge the two lists then sort ?
You the GOAT.
hi just curious why did you return dummy.next not tail.next?
pulling my hair because of this
why does the following for the while loop part not work? why do i need the else statement?
while list1 and list2:
if list1.val > list2.val:
print(list2.val)
tail.next = list2
list2 = list2.next
if list1.val
Hi, just asking for clarification: I understand when we initialize dummy, it starts with a node of value 0, as per the __init__() dunder method. So when we return dummy.next, we ignore the initial node, since that's not part of either l1 or l2.
But doesn't .next typically refer to the "next node in the linked list", as opposed a "list of nodes where the head is discarded"? Rather, if you don't assign dummy = dummy.next for example, is that what I should expect? So dummy.next.next would return a Linked List object, with the head and the node that the head is pointed to removed?
Finally, would a more intuitive implementation be having set the init self.val = None, and then returning dummy, not dummy.next? I am self teaching myself DSA and programming in general, so apologies if my question sounds incoherent.
@avfr thanks!@
@avfr thanks for the clarification.
ruclips.net/video/-Cjgt5I0YvM/видео.html - this solved my doubts
How to insert elements in list to linked list?
Time: O(N), Space: O(N+M). Is this correct?
I think the space should be O(1) because we are only making the new dummy node and connecting the already existing nodes. The input size wouldn't change how much extra space we need for the function.
this is iteration version..do you have recursion one?
It's the solution provided by LC
class Solution:
def mergeTwoLists(self, l1, l2):
if l1 is None:
return l2
elif l2 is None:
return l1
elif l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
thank you!
I am totally new with LinkedList: Can anyone help me understand why do we need a dummy node here?
There's something that's confusing me. What if one list is null and the other still has multiple nodes remaining? Wouldn't the second half of the code need to be inside another while loop? Otherwise, isn't your code just adding 1 of the remaining nodes onto the merged list and leaving however many were left floating?
Each node has a next property which points to the next node, so by adding just the next node of the remaining list, you 'automatically' add the rest of that list since that node that you added points to the next one, which points to the next one, etc.
@@damienbabington6765 OHHHHHH, that makes sense! I had a suspicion but wasn't 100% sure on it. Thank you so much for the clarity!
i cant wrap my head around "return dummy.next" what happens. why isnt it null?
Not gonna lie, this list thing is kinda going over my head a little bit, I am trying but it's a bit difficult
I am very new to python and coding. One question I have is, why you do not need to pass tail back to dummy?
i just got it myself. the nodes each point to the same literal data. so when you make dummy it points to the same thing as tail, as you change tail dummy still points to everything tail points to because dummy is the first node and points to the second (where tail starts creating nodes).
this is the harshest wake up call that your variables do not store your data they just point to it SMH
Why is it tail.next = l1 (or l2) and instead tail = l1 (or l2)
Can someone tell me why this is wrong? Trying to understand how linked lists work.. class Solution(object):
def mergeTwoLists(self, list1, list2):
dummy = ListNode()
f = dummy
while list1 and list2:
if list1.val < list2.val:
f = list1
list1 = list1.next
else:
f = list2
list2 = list2.next
f = f.next
if list1:
f = list1
elif list2:
f = list2
return dummy
I am getting invalid syntax for line 8
I'm watching these videos for my own interview and I'm glad he got a job. Cause he sounds so dead at the beginning
When will I start to understand how to do this I watched 3 of his videos and everytime I watch I’m confused asf
Can't understand how does it work with commented class Listnode o_O
Anyway mine doesn't work both ways.=(
Can I ask a stupid question here? Why I can't merge two list and use sort()?
You are working with ListNode objects, not regular lists, so there is no sort method.
At the start of the solution, why hasn't he just written "tail = ListNode()"...???
Can someone explain why we don't want to insert into an empty list?
apparently, because we need to keep the same nodes, but rather reassign the pointers in such a way that they'll end up making a big linked list
def mergeTwoLists (self, l1:ListNode , l2 : ListNode ) -> ListNode:
what is the error here ??
do it in python not in python 3
i dont know why leetcode put this problem in resursion section
thanks
shouldn't we do it in constant space? what's the fun when we use extra space?
Why first node have to be dummy in output?
dummy is the FIRST node. Tail is used as a Reference node which moves from dummy to all the other nodes(in order to point to the next one). in other words, since Linked list works needs a starting node to be able to point to the next, we create Dummy which is supposed to be fixed at beginning and cant be used for traversal.
bro this is my code:
class Solution(object):
def mergeTwoLists(self, lists1, lists2):
dummy = ListNode()
tail = dummy
while lists1 and lists2:
if lists1.val < lists2.val:
tail.next = lists1
lists1 = tail.next
else:
tail.next = lists2
lists2 = tail.next
tail = tail.next
break
if lists1:
tail.next = lists1
elif lists2:
tail.next = lists2
return dummy.next
it's not giving me the correct answer, the output I got is [1,1,2,4] here only my first list is working but not the second can you help me, please.
Can you please explain the space complexity of this solution? isn't O(n) as because of dummy node?
yeah space complexity is O(n).
because we are creating a new list.