Merge Two Sorted Lists - Leetcode 21 - Python

[@NeetCode]

🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤

[@piyushgupta4849]

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

[@ngndnd]

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

[@RugvedhTallapudi-lk9jy]

Super bro . But how I too was learning but this is too difficult

[@sparrow2068]

But u still got it wrong 😂

[@Humon66]

@@sparrow2068 Laughing at others' efforts. Heartless boy.

[@sparrow2068]

im sorry@@Humon66

[@NguyenLe-nw2uj]

@@sparrow2068 hope with that you feel better

[@siddharthsaravanan7075]

- 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

[@jey_n_code]

it is O(n+m) space complexity, there is literally new list created

[@KCIsMe]

@@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.

[@j20py56]

Wouldnt memory be O(max(n,m)) since the call stack can have up to max(n,m) recursive calls * O(1) operations each?

[@louisuchihatm2556]

@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.

[@JefferVelezE]

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("*****")

[@sesquipedaliansophistry]

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...

[@b1ueberrycheesecake]

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

[@varunshrivastava2706]

I found LinkedList really confusing in python, mainly because I can't visualize it while coding.

[@willowsongbird]

@@varunshrivastava2706 me too

[@I3uzzzzzz]

@@willowsongbird didnt ask. ruth.

[@feijaodo]

@@varunshrivastava2706 I'm still very confused about this whole dummy list thing.

[@rajatnayak972]

​@@varunshrivastava2706 do you have any python recommendatios for same?

[@sauravdeb8236]

This channel is so underrated.

[@fattysun1121]

fr

[@lawrencek.5342]

very like the graphic introduction before coding, which makes me easy understand what the entire code is doing

[@mostinho7]

Done thanks Todo:- implementation copy to notes Again using the dummy head technique to avoid edge cases similar to delete node

[@geekybox52]

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.

[@hasanbohra6779]

Thanks a lot!!! finally understood how it works🫡

[@JoshPeterson]

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.

[@MrClimberarg]

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.

[@trivialnonsense]

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?

[@jeffreysneezos]

Hey @trivialnonsense, did you end up finding this out? I'm stuck on the same thing...

[@manishmaurya857]

does anyone know ?

[@iiiiilllllllll]

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

[@mio1201]

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

[@adefela]

Your reply help me, thank you!@@mio1201

[@DarkDiegon]

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?

[@suhasshetty6607]

Tail starts from the dummy node, thats why tail is assigned to dummy.

[@mr_matata]

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

[@varunnarayanan781]

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!

[@thilinarajapaksha6361]

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))

[@amitjha9747]

@@varunnarayanan781 yes that’s correct

[@nitiketshinde1458]

*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

[@frankl1]

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)?

[@primogem_160]

@@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| ) ??????

[@frankl1]

@@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?

[@primogem_160]

@@frankl1 agreed.

[@licokr]

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!

[@peter8892]

Good explanation. This is similar merging technique done in the merging part of merge sort

[@psibarpsi]

Exactly.

[@kavan3]

I understood this part of the prompt; "The list should be made by splicing together the nodes of the first two lists"; to mean that you could not create a new starting ListNode and then append to that from either list. So I started with my head pointer to either list1 or list2 depending on which is smaller and then merged the two lists from there

[@anuragsuresh5867]

Bruh, I did this problem without making a new list. I knew it seemed too hard for an easy,

[@aniketsrivastava7968]

Same thing happened to me bro :( I spent almost 2 hrs on this.

[@varunshrivastava2706]

@@aniketsrivastava7968 Linked lists are tough!! I guess now you have become comparatively good at it. Since you saw this video 3 months ago?

[@faizikhwan_]

Why are we returning dummy.next while the value for dummy is not update after it initialise(line 8)?

[@feijaodo]

still do understand that at all

[@BielzGamer]

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

[@REPLICASINSIDE]

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

[@LamNguyen-nm1id]

why did i ever think inserting from one list into another would be easier, dummy node sure makes thing so damn simple

[@tahichy9169]

Could you please make a playlist for recursion?

[@compsbecomping]

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...

[@UnfinishedYara]

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!

[@compsbecomping]

Same to you. We'll get there eventually!

[@wilsonwang8641]

The part between line 20 to 23 can be simplified to tail.next = l1 or l2.

[@SohelKhan-vt5ql]

does it work on c++?

[@NilAtabey]

criminally underrated. thank you

[@jonintc]

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.

[@aoshow_33]

How would we do this without creating a new linked list?

[@dev-skills]

I found the approach of using dummy node very clean

[@baharrezaei5637]

Such a useful source of learning. Well done. Thank you very much for sharing 🌷

[@jameszhang8569]

the 'dummy and tail' technique is really the key.

[@musicgotmelike9668]

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!

[@PiyushSingh-bi9kn]

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.

[@Historyiswatching]

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!

[@CostaKazistov]

tail = last node It's by convention. Have seen it in many data structure tutorials and books. Seems common across languages - Python, Kotlin, Java.

[@madhavkwatra5888]

You made it so easy . WOW man. Thanks

[@_ipsissimus_]

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

[@jideabdqudus]

you're returning dummy.next because when you intialized the list it has an extra node in the beginning called the "dummy" node

[@feijaodo]

i don't even understand why their returning dummy at all, it was never updated or changed since it initialized WTF

[@dnm9931]

@@feijaodoyou find the answer for this? I’m stuck here too

[@spencersedano]

@@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.

[@gunahawk6893]

congrats on 100k bruh , u deserved it

[@simonedellalibera]

I was about to write and insanely long comment because I got confused so many times when drawing the solution and I couldn't understand some steps, but now I finally got it. The only thing that makes me feel sad is that I am studying for my DSA exam and am I also working at a big tech company (thanks god in a Low-code team) but I feel so much guilt because yes, I am able to fully understand these kind of exercises, but when I have to implement them I panic or just can't thing of the right solution (what I mean is that I understand easily the solution but I can't think of it on my own). Is it just a matter of practice? Consider I am a student/worked at his first big job. I feel like I can't think of these small tricks that helps solve the problem like the dummy thing. Is there a way to approach mentally these questions?

[@phoenixpagan4431]

Can you clarify why you return dummy.next instead of tail or tail.next? Thanks in advance

[@NeetCode]

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]

@@NeetCode But when was dummy.next ever assigned to?

[@guiningotoshuki3845]

​@@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-el6oy]

@@guiningotoshuki3845 so when he did tail = dummy, he made dummy point to tail?

[@sravanikatasani6502]

@@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.

[@mmmk1414]

this was kinda helpful, mainly because the concept o f linked lists is new to me

[@mberu14]

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

[@marianpascu8474]

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??

[@gokusaiyan1128]

Why are we returning dummy.next ? Isn't dummy equal to empty node. Also we never set dummy.next = tail.

[@HuyNguyen-zp8ju]

this approach is awsome and easy to understand, Thank you Neetcode

[@spongbob496]

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"

[@edtaskin4117]

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.

[@AgentRex42]

Hi, thank you for your videos. Which software do you use to make your videos ?

[@CostaKazistov]

Microsoft Paint 3D

[@lee_land_y69]

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?

[@thilinarajapaksha6361]

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}

[@Chris-kx7xj]

Wouldn't the time complexity be O(min(m, n)) since the while loop only iterates until the smaller of the two lists ends? Then if there is any remainder from either list it just gets tagged on at the tail, which I'm pretty sure takes constant time.

[@JacquesAsinyo-e5i]

Thank you so much man!!!

[@seancrawford477]

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

[@bigrat5101]

Hi NeetCode, you videos helped me so much. thank you! do you mind create a video for basic calculator problem on leetcode?

[@neoplumes]

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

[@josephsatow482]

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

[@spongbob496]

Hi did you ever figure this out? I'm struggling on the same concept! Thanks!

[@guitarman2501]

​@@spongbob496 Nah, I still need clarification on this concept haha

[@jesuscruz8008]

love your content boss glad i found your channel!

[@НикитаБуров-ъ6р]

while list1 AND list2, omg, it took me an hour to find this mistake

[@aaen9417]

As always, thanks for the great explanation. Cheers my friend

[@ajaydhanwani4571]

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?

[@lovenangelodayola1826]

I am also confused, do you now know the explanation?

[@REPLICASINSIDE]

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.

[@neighboroldwang]

I still don't quite get it. The problem description asks us to return the head. The merged linked list is the head?

[@adamrao6161]

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]

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!

[@HsiaoyuanA92]

@@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!

[@_7__716]

@@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.

[@LAFLAME1111]

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?

[@darellarocho5729]

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?

[@damienbabington6765]

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.

[@darellarocho5729]

@@damienbabington6765 OHHHHHH, that makes sense! I had a suspicion but wasn't 100% sure on it. Thank you so much for the clarity!

[@diftq8191]

tail is an empty listnode so tail = tail + 1 doesn't do anything or will give an error? Shouldnt tail = l1.next be enough?

[@kokosda]

I love that dummy technique.

[@AgentRex42]

Hey, why do we need to use tail ? Why can't we use directly dummy ?

[@farazahmed7]

Then how will you know which one is the first node?

[@AgentRex42]

@@farazahmed7 I don't understand...

[@vanchark]

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.

[@adityachache]

The tail can also be called the currentnode which you will be updating

[@ehsanmon]

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!

[@AbsThePunisher]

Could you explain. why tail = dummy line?

[@akx_edits3374]

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.

[@nivedithabaskaran1669]

Time: O(N), Space: O(N+M). Is this correct?

[@tonynguyen6124]

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.

[@zayarlyn]

Clear explanation! Thanks.

[@areebhussainqureshi5400]

Can somebody please elaborate on tail = dummy? How come returning dummy .next works but not tail .next when we equated them at the start.

[@vansh9857]

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.

[@dnm9931]

@@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

[@SaraH-dj8xg]

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)?

[@akashsaha905]

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.

[@cipherbenchmarks]

What software do you use for hand solving problem sets?

[@suryadevarakarthik1814]

Does dummy mean head node?

[@sravanikatasani6502]

yeah sort of , dummy is pointing to the head of merged list.

[@adityachache]

It's like you're creating another list to store all those nodes and then return that list

[@kwakubiney5175]

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?

[@momtheplum185]

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

[@reviews9216]

​@@momtheplum185 Thank you. Could you please elaborate. If i use just return dummy, it returning a zero at the begging. Why ?

[@blueskies3336]

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)?

[@0mara.fattah261]

I think tail is a pointer to a node, and in python you don't need to specify the type of the variable

[@khoapham7303]

Why do we need the code `tail = dummy` at the 2nd line? I'm still confused with it.

[@skepziev2565]

that's what Im saying. I get that the dummy is supposed to be the result linked list after the logic, but why do we need to set tail = dummy???

[@Emorinken]

Thank you very much

[@mawhadmd]

I don't understanding the last part, you only assign tail.next=l1; this will only take one number from l1? it's not a loop

[@REPLICASINSIDE]

there's a dummy node which does that work for you.

[@ChenxiZhang168]

how do u solve the problem without a dummy node? I'm still kind confused abt the dummy node

[@razorhxh7371]

Guys this is def not an easy question. Would prob put this medium

[@ngochainguyen91]

Please...! Can someone clear Why dummy=tail return dummy is Correct Ans But return tail -> result is [4,4]

[@si-fi]

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.

[@ngochainguyen91]

@@si-fi still don't really understand :(. In this time right line we return dummy, tail is [4,4].

[@nadirelc]

@@ngochainguyen91 i still stuck with this, do you understand now? can you explain it to me?

[@sambanaei2984]

Thanks!

[@vishetube]

Where you setting dummyNode.next to tail? how do they directly referenced?

[@siddhigolatkar8558]

Thank you

[@noshina04]

after torturing myself to solve this in eclipse using linked list built in methods i am here for the python solution.

[@mohamedantar1249]

Thanks a lot

[@niyantazamindar4019]

You the GOAT.

[@symbol767]

Ty bro, liked.

[@Shanky_17]

nice explanation buddy !!

[@yapyapYap-ry3no]

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?

[@ahmedanwer6899]

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

[@danielyang3118]

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.

[@moosegoose1282]

@avfr thanks!@

[@user-us4mc7ej3c]

@avfr thanks for the clarification.

[@abishekbaiju1705]

kzbin.info/www/bejne/Y3TNmKdrfpWMrK8 - this solved my doubts

[@vivekanpm3130]

Can anyone explain why we name dummy as tail ?

[@_slier]

this is iteration version..do you have recursion one?

[@orangethemeow]

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

[@HamidKabia]

Can someone explain what the listnode is and how it works

[@SaceedAbul]

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

[@Kim-tr5op]

i cant wrap my head around "return dummy.next" what happens. why isnt it null?

[@erharman27]

But you are not using the Original Lists... you are creating a new one??

[@rayyan-munassar]

# Can some one explain to me why this is the behavior of the code: while l1 and l2: if l1.val

[@kashifahmed_1995]

Thank you for the neat explanation

[@kashifahmed_1995]

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 ❤️

[@SajidAli-fn9tp]

@@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.

[@whalingwithishmael7751]

Why am I not able to print(list1.val)?

[@maamounhajnajeeb209]

thanks

[@danielsun716]

recursive version: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: if not list1: return list2 elif not list2: return list1 elif list1.val list2.val: list2.next = self.mergeTwoLists(list1, list2.next) return list2