Merge Two Sorted Lists - Leetcode 21 - Python

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.

[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

[siddharthsaravanan]

- 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

[bueberrycheesecake]

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

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


node3 = ListNode(val=3, next=None)
print('node1 val', node1.val)
print('node1 next', node1.next)
print(id(node1), id(node2))


node2.next = node3
node2 = node3
print('node1 val', node1.val)
print('node1 next', node1.next.val)
print(id(node1), id(node2))

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

[lawrencek.]

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

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

[mostinho]

Done thanks
Todo:- implementation copy to notes

Again using the dummy head technique to avoid edge cases similar to delete node

[peter]

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

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

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

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

[anuragsuresh]

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

[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

[musicgotmelike]

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!

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

[baharrezaei]

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

[faizikhwan_]

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

[geekybox]

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

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