Merge Two Sorted Lists - Leetcode 21 - Python
Vložit
- čas přidán 9. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Twitter: / neetcode1
Discord: / discord
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
Problem Link: neetcode.io/problems/merge-tw...
0:00 - Visual Explanation
3:15 - Coding Optimal Solution
#leetcode #microsoftcodinginterview #linkedlist
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
🚀 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.
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
Hi NeetCode, thanks again for this. The suggestion would be to do all the problems from the 75 Must Do Leetcode list. By the way, I discovered that list by your suggestion and it's great.
very like the graphic introduction before coding, which makes me easy understand what the entire code is doing
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.
Such a useful source of learning. Well done.
Thank you very much for sharing 🌷
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
Done thanks
Todo:- implementation copy to notes
Again using the dummy head technique to avoid edge cases similar to delete node
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
Clear explanation! Thanks.
Good explanation. This is similar merging technique done in the merging part of merge sort
Exactly.
I found the approach of using dummy node very clean
What software do you use for hand solving problem sets?
love your content boss glad i found your channel!
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
As always, thanks for the great explanation. Cheers my friend
How would we do this without creating a new linked list?
Difficulty doesn't matter. Your explanation and code are shine even in easy problems. using dummy and appending a remain node in the end, it's absolutely amazing. Thank you very much!
this approach is awsome and easy to understand, Thank you Neetcode
Hi, thank you for your videos. Which software do you use to make your videos ?
Microsoft Paint 3D
criminally underrated. thank you
congrats on 100k bruh , u deserved it
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?
Hi NeetCode, you videos helped me so much. thank you! do you mind create a video for basic calculator problem on leetcode?
Could you please make a playlist for recursion?
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.
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 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?
Thank you so much man!!!
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
this was kinda helpful, mainly because the concept o f linked lists is new to me
Where you setting dummyNode.next to tail? how do they directly referenced?
nice explanation buddy !!
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 for your explanation! I was trying to merge list1 into list2 for so long, but here so many edge cases and I thought to myself: This can't be that difficult. As it turns out, it isn't:) Thanks a lot!
did the same thing, and finally ended giving up, glad I arrived here, because the approach is completely different than where I was stuck at.
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.
Ty bro, liked.
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??
why did i ever think inserting from one list into another would be easier, dummy node sure makes thing so damn simple
thank you!
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🫡
*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.
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}
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.
The part between line 20 to 23 can be simplified to tail.next = l1 or l2.
does it work on c++?
how do u solve the problem without a dummy node? I'm still kind confused abt the dummy node
I still don't quite get it. The problem description asks us to return the head. The merged linked list is the head?
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.
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?
I love that dummy technique.
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.
czcams.com/video/-Cjgt5I0YvM/video.html - this solved my doubts
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.
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!
Why do we need the code `tail = dummy` at the 2nd line? I'm still confused with it.
How to insert elements in list to linked list?
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
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.
can someone explain why we need to create dummy? instead tail = ListNode(), is it tail and dummy share of instance of ListNode(). ~confused
Can anyone explain why we name dummy as tail ?
You the GOAT.
while list1 AND list2, omg, it took me an hour to find this mistake
Thank you
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.
Can we say time and space complexities are O(n+m) (n being the length of list 1 and m being length of list 2)?
Time complexity would be O(min(n,m)) because once one of the list's becomes null then we can just make our main list point to the other list.
Can someone explain what the listnode is and how it works
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
Hi,
I am getting below error:-
if l1.val < l2.val:
AttributeError: 'LinkedList' object has no attribute 'val'
can you help me on this?
you have to change the values at the very start, they are by default list1 and list2.
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 ?
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.
Why are we returning dummy.next ? Isn't dummy equal to empty node. Also we never set dummy.next = tail.
thanks
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
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.
I am getting invalid syntax for line 8
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
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().
Guys this is def not an easy question. Would prob put this medium
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!
Can't understand how does it work with commented class Listnode o_O
Anyway mine doesn't work both ways.=(
I am totally new with LinkedList: Can anyone help me understand why do we need a dummy node here?
after torturing myself to solve this in eclipse using linked list built in methods i am here for the python solution.
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.
i cant wrap my head around "return dummy.next" what happens. why isnt it null?
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.
Does dummy mean head node?
yeah sort of , dummy is pointing to the head of merged list.
It's like you're creating another list to store all those nodes and then return that list
I LOVE YOU!
... for explaining the problems and their solutions so well - and I meant it in a strictly in a most heterosexual way.
lol
I xopied the same xose .It didnt work
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.
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
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
If you struggled with this question and feel bad because it's marked easy, DON'T!
It's more like a medium in my opinion. Plus, linked lists tend to be really confusing in the beginning, so just keep practicing and it will get better!
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
What's the space complexity?
understood
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
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
Hi NeetCode, can I solve this by converting the 2 linked lists to an array, sorting the array and then looping through the array to form a new linked list