Understooooooooooooooood? . Instagram(connect if you want to know how a SDE's normal life is): @t . . If you appreciate the channel's work, you can join the family: @t
@sans.creates3 жыл бұрын
yessss
@subhamengine11433 жыл бұрын
just watched the first 3 min and tried myself..and it was a successful submission.
@PrinceKumar-el7ob3 жыл бұрын
i don't know why striver over complicated it!! but still after watching flattening of linked list i got the idea here is my code for future reference. if(head1==NULL) return head2; if(head2==NULL) return head1; Node *res=new Node(-1); Node* temp=res; Node* l1=head1; Node* l2=head2; while(l1 && l2){ if(l1->datadata){ temp->next=l1; l1=l1->next; } else{ temp->next=l2; l2=l2->next; } temp=temp->next; } if(l1) temp->next=l1; else temp->next=l2; return res->next;
@rohansinha27603 жыл бұрын
For merge method, without interchanging l1 and l2, just shifting the pointer would work. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next def merge2Lists(self, l1, l2): head = point = ListNode(0) while l1 and l2: if l1.val
@AlbertoRodriguez-oe6jo3 жыл бұрын
The swapping feels like over-complicating simple algorithm, for me this approach works better: if(l1->val < l2->val){ temp->next = l1; l1=l1->next; } same for l2 is more intuitive.
@PrinceKumar-el7ob3 жыл бұрын
Now i understand what you were saying i don't know why striver overcomplicated it!! but still after watching flattening of linked list i got the idea here is my code for future reference. if(head1==NULL) return head2; if(head2==NULL) return head1; Node *res=new Node(-1); Node* temp=res; Node* l1=head1; Node* l2=head2; while(l1 && l2){ if(l1->datadata){ temp->next=l1; l1=l1->next; } else{ temp->next=l2; l2=l2->next; } temp=temp->next; } if(l1) temp->next=l1; else temp->next=l2; return res->next;
@SaumyaSharma0072 жыл бұрын
@@PrinceKumar-el7ob thanks bro i have coded with the same approch
@amitarya48942 жыл бұрын
@@PrinceKumar-el7ob same here bro
@happy_soul1842 жыл бұрын
@@PrinceKumar-el7ob he is not overcomplicating it idiot he is telling u optimal approach that takes less space
@hamdanahmad667 Жыл бұрын
could you please tell me what is the difference between strivers first approach and this approach as you are also creating a dummy node like him
@coding64093 жыл бұрын
A little modification ... We don't need to do tmp = nullptr always, it works fine ! Great video btw! Could not find such a clear explanation anywhere!!
@premanshdewangan86953 жыл бұрын
Its always a good practice to initialize ur pointer with NULL to avoid memory leakage. However, it happens very rare, when u are dealing with complex programs.
@settyruthvik62363 жыл бұрын
#code in python # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # @param A : head node of linked list # @param B : head node of linked list # @return the head node in the linked list def mergeTwoLists(self, A, B): dummy=ListNode(0) curr=dummy while A and B: if A.val>B.val: curr.next=B B=B.next curr=curr.next else: curr.next=A A=A.next curr=curr.next if not A:#end of A curr.next=B B=B.next else: curr.next=A A=A.next return dummy.next
@vikashkumarmahato6461 Жыл бұрын
here in the last two if -else statement we dont need to move A and B to next .It works without moving to next
@hrithikrudra42924 жыл бұрын
Bhaiya, please complete the DSA sheet fast..🙏🙏🙏
@arjeriaharsh13 ай бұрын
In Java code, just add null check for the swap after the inner while loop.
@infinioda1082 жыл бұрын
Without interchanging the l1 & l2 too, we can easily do this.
@mukeshbalaji043 жыл бұрын
"Thissss iss the moment".... 😎😎
@adityaajay292 жыл бұрын
in case you don't wanna manipulate l1 and l2, try this instead, btw understood :) ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { if(list1 == nullptr) return list2; if(list2 == nullptr) return list1; // assuming list1->val is smaller ListNode *small = list1; ListNode *large = list2; // assigning small to whichever is smaller if(list1->val > list2->val) swap(small, large); ListNode *head = small; while(small != nullptr && large != nullptr) { ListNode *temp = nullptr; while(small != nullptr && small->val val) { temp = small; small = small->next; } temp->next = large; swap(small, large); } return head; }
@prakharsankrityayan13003 жыл бұрын
Shouldn't the time complexity for the first approach be O(min(n1,n2))?
Yes but you're using recursion which uses stack, so the space complexity would be O(n).
@ayesharashid9629 Жыл бұрын
code for 1st solution function merge(L1, L2) { // create new linked list pointer var L3 = new Node(null, null); var prev = L3; // while both linked lists are not empty while (L1 !== null && L2 !== null) { if (L1.data
@shreyapaul72572 жыл бұрын
Probably the best explaination I have seen on the internet so far !!!
@juhisingh45093 жыл бұрын
One of the best Explanation. Your way of explaining concept is amazing. You are my motivation.
@ankitkumaryadav5622 жыл бұрын
with external space wala technique me time complexity to min(n1, n2) hoga q ki minimum value tak to dono while loop me chale ga uske baad to direct value assigned kr dena hai an last node ke pointer me
@baljotsinghchoudhary74344 жыл бұрын
very complex solution simply use the logic of merge in merge sort
@@baljotsinghchoudhary7434 This is O(n) space solution which he told before! He optimized it bro
@ragnarT33 жыл бұрын
@@coding6409 nop dude watch some space complexity videos... It is constant space
@ravipatiramya41853 жыл бұрын
@@baljotsinghchoudhary7434 can u give brute Force approach
@arjunkhanna18032 жыл бұрын
The recursive code to sort in place is much easier
@prakharsankrityayan13003 жыл бұрын
Why should the space complexity for the first approach be O(n1+n2)? We are just creating a new node d and then attaching the existing nodes to that (In sorted order obviously). So we aren't using any new space right? So shouldn't the space complexity be O(sizeof d) ? Correct me if I'm wrong. TIA.
@namansharma51282 жыл бұрын
The approach he talked about is making new nodes but YES we can just point the nodes in correct order in place of creating the new nodes and assigning it the values.
@avinash-xh6qw3 жыл бұрын
how does the swap function work over here? @take U forward
@shikharsrivastava73122 жыл бұрын
best explanation. tc of the first approach will only be o(length of smaller linked list)?
@tanishqua391 Жыл бұрын
why did we create a dummy node in the first approach ..we could've just moved duplicate dummy across our linked list?
@travelnlearn2 жыл бұрын
You made dsa easier and fun2 learn Thank You sir Love you may gbu with lots of succcess happiness love health and peace
@DroidHolicOfficial2 жыл бұрын
Here is how I implemented the in-place approach in JS function mergeLists(head1, head2) { let l1 = head1.data < head2.data ? head1 : head2; let l2 = head1.data < head2.data ? head2 : head1; let result = l1; let prev = null; while(l1){ if(l1.data
@amitghosh45484 жыл бұрын
What if I use recursion approach without using any external space instead of iterative way?
@takeUforward4 жыл бұрын
recursion uses stack space
@EverythingFootball03113 жыл бұрын
@@takeUforward no we can do it without space using recursion
@ng3w4623 жыл бұрын
@@EverythingFootball0311 how though?
@masterroyjones42283 жыл бұрын
If you are not using any extra stack then also call stack is used which is calculated in space complexity so if someone ask recursion sc its always maximum call size
@rishabhkesarwani57613 жыл бұрын
I have a much simpler solution of this question this solution is very much similar to the merging of two sorted arrays Java Solution class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode head=new ListNode(-1); ListNode curr=head; while(l1!=null && l2!=null){ if(l1.val
@mayuprsv89902 жыл бұрын
He trying to explain inplace solution and your will have additional space complexity which he already explain first part of video
@namansharma51282 жыл бұрын
@@mayuprsv8990 No bro, this is also with constant space complexity, he is using only some variables. Can u plz tell how additional space is used here ??????
@namansharma51282 жыл бұрын
I also thought the same way, idk why has he made it so complicated.
@mohammadthousif38692 жыл бұрын
What's the space complexity of your code ??
@epictube5045 Жыл бұрын
your code will not work for all test cases because as soon as u come out of your loop you are expecting only one element left in either of your linked lists
@Rohit_IITBHU10 ай бұрын
solution with using dummy node has space complexity is O(1) You have told it in new video I m confused now
@praptiluthra1632 жыл бұрын
why do we create a dummy node in the start? why can't we just keep head, tail pointers for a new list (additional space list).
@sayantaniguha85192 жыл бұрын
This approach is just so much better and understandable
@NagaVijayKumar4 жыл бұрын
Thank you bro.. For uploading multiple videos in a single day..
@cenacr0072 жыл бұрын
tbh using the same logic as merging sorted array would be better, swap is too much complicated I guess.
@aakashyadav62283 жыл бұрын
Bhai please complete the series. I have my placement in next 2 months and it all depends on you now. Please Please Please.
@sathishkumar-dc9ce3 жыл бұрын
which clg bro?
@anubansal24624 жыл бұрын
Shouldn't be the time complexity as min(l1, l2) ?
@Mutant233 жыл бұрын
No because imagine the case 1->10 and 2->3->5->6->7 In this case we traversed the whole long list so time complexity is worst case will be O(n1+n2) only
@kapilpatel93792 жыл бұрын
When we do swap, doesn't that get counted as memory usage?
@ranasauravsingh2 жыл бұрын
UNDERSTOOD... !!! Thanks striver for the video... :)
@bloody91622 жыл бұрын
Space complexity for the solution creating a new LinkedList won't be linear even if you create a new linked list mate, it will be constant.
@cenacr0072 жыл бұрын
prev LL is left as it is and new nodes are created, ofc space comp would be linear in the first approach, if we don't create new nodes and just change links only then space comp is constant.
@bloody91622 жыл бұрын
@@cenacr007 free the memory that is held by the prev LL as you go. There's no need to hold that memory. Of course this should not be the ideal way, i.e changing the input. But it won't change the fact that the space complexity would be constant.
@AnujGupta-fp1mv Жыл бұрын
Bro what if List1 is 1, 2, 3 and list2 is 4, 5, 6, 7 then in the inner while loop l1 will point to null in l1=l1.next then interchanging the l1 and l2 will point to null then why it is again going in the loop?
@992_anisharoy9 Жыл бұрын
Thank you for such a wholesome explanation.
@okey13172 жыл бұрын
i know how it works,, but cant visualize well, expecially the end conditions 😪😪😪
@sauravjha552 Жыл бұрын
Can I get a code with extra space?
@Adityadekhrahahai3 жыл бұрын
in leetcode it is showing Runtime error when this code is implemented , can u tell mewhat is the wrong thing in this code ?
The best thing this guy is doing honestly apart from his awesome explanation is that he is not giving away the code! Respect++;
@SatyamKumar-bw4vi2 жыл бұрын
wah Jhaji!
@adi5962 Жыл бұрын
Chat gpt pe mil jayega code ab
@shreyasingh78333 жыл бұрын
Thanks for such a clear explnation..
@newgamers4392 жыл бұрын
Thanks for the precise concept.
@akshatsamdani Жыл бұрын
Here is the simpler version of this code: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { // if list1 happen to be NULL // we will simply return list2. if(list1 == NULL) return list2; // if list2 happen to be NULL // we will simply return list1. if(list2 == NULL) return list1; ListNode* newHead = NULL; if (list1->val < list2->val) { newHead = list1; list1 = list1->next; } else { newHead = list2; list2 = list2->next; } ListNode* prev = newHead; while (list1 != nullptr && list2 != nullptr) { if (list1->val < list2->val) { prev->next = list1; list1 = list1->next; } else { prev->next = list2; list2 = list2->next; } prev = prev->next; } // adding remaining elements of bigger list. if(!list1) prev -> next = list2; else prev -> next = list1; return newHead; }
@devpant78292 жыл бұрын
Priya mujhe pata hai tumhara linked list weak the... I still miss you priya please unblock😣
@yashsingh9882 Жыл бұрын
Can someone please provide the java solution for the first algo that used external space?
@tauhait4 жыл бұрын
Simply superb!!
@rohithbharathi3664 Жыл бұрын
U are explanation is very good but one thing please don't shout at me 😂
@m4n0jkum4r2 жыл бұрын
This code doesn't consider the duplicate elements.
@govi4565 Жыл бұрын
why are we swapping at the end here? anyone??
@vagabondfoodie5788 Жыл бұрын
its basically because of else condition, iF ( l1>L2) THEN WE HAVE TO SWAP THEM
@disharastogi56092 жыл бұрын
very nice approach!!
@kaichang8186Ай бұрын
understood, thanks for the great explanation
@sarahdaniel68623 жыл бұрын
👏👏👏 Clearly understood
@Pa1n_xd Жыл бұрын
Why do we need to complicate it by swapping l1 every time simple ptr swap works ?? c++ class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if(l1==NULL)return l2; if(l2==NULL)return l1; ListNode*zero=new ListNode(0); ListNode*zerohd=zero; while(l1!=NULL && l2!=NULL){ if(l1->valval){ zero->next=l1; zero=zero->next; l1=l1->next; } else { zero->next=l2; zero=zero->next; l2=l2->next; } } if(l1!=NULL){ zero->next=l1; } if(l2!=NULL){ zero->next=l2; } return zerohd->next; } };
@curs3m4rk3 жыл бұрын
Super video! I applauded for ₹40.00 👏
@arunsuthar478310 ай бұрын
in javascript
@PinaColada652 жыл бұрын
this video is very helpful to me..thnks
@mmbmmbmmb Жыл бұрын
thank you so much
@satyamgupta6030 Жыл бұрын
ultimate explaination thanks alot striver
@hmh70282 жыл бұрын
You have complicated this question too much
@satya10673 жыл бұрын
❤️❤️❤️❤️❤️❤️
@ankitkumaryadav5622 жыл бұрын
Without Swaping the node My Solution ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (l1 == NULL) return l2; if (l2 == NULL) return l1; ListNode* root; if (l1->val val) root = l1; else root = l2; ListNode* temp = NULL; while(l1 && l2) { if (l1->val val){ if (temp != NULL) temp->next = l1; temp = l1; l1 = l1->next; } else{ if (temp!=NULL) temp->next = l2; temp = l2; l2 = l2->next; } } if (l1) temp->next = l1; if (l2) temp->next = l2; return root; }
@indra162 жыл бұрын
out standing
@aayushsharma98173 жыл бұрын
great explanation
@shashankgsharma09013 ай бұрын
Understood!
@16avikasgupta702 жыл бұрын
Thanks buddy for your help
@Dsa_withjay8 ай бұрын
mind blowing !! bhayi really maza agyaa...!🥵
@uttamchandraketu2816 Жыл бұрын
You made too complicated in both approaches
@roliverma58513 жыл бұрын
Amazing!
@largemars16424 жыл бұрын
Sir aap Hindi me classes kariye na
@takeUforward4 жыл бұрын
Community post pdho
@mehak_mits Жыл бұрын
Understood
@mmbmmbmmb Жыл бұрын
understood
@naman_goyal4 жыл бұрын
Nice Bruh
@om_1_24 жыл бұрын
Thanks broo👍👍👍
@chirag_ccp2 жыл бұрын
Instead of using std::swap, If I define my own swap() function as void swap(ListNode* a, ListNode* b) { ListNode* temp = a; a = b; b = temp; } It doesn't get swapped. Can anyone explain the reason ?
@aayush54742 жыл бұрын
copy of pointer is being passed. Pass a pointer to a pointer to make it work
@adis68672 жыл бұрын
L1 and L2 is already a pointer, so you need to pass it by address. i.e swap(&l1,&l2). And in swap function double pointer will come.
Is this approach optimal? class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode* a = l1; ListNode* b = l2; ListNode* head = new ListNode(-1); ListNode* temp; if(l1==nullptr && l2==nullptr) return nullptr; else if(l1==nullptr) return l2; else if(l2==nullptr) return l1; else { if(a->val < b->val) { temp = a; a = a->next; } else { temp = b; b = b->next; } head->next = temp; while(a!=nullptr && b!=nullptr) { if(a->val < b->val) { temp->next = a; a = a->next; temp = temp->next; } else if(a->val > b->val) { temp->next = b; b = b->next; temp = temp->next; } else { if(temp->next == b) { temp = temp->next; b = b->next; temp->next = a; temp = temp->next; a = a->next; } else { temp = temp->next; a = a->next; temp->next = b; temp = temp->next; b = b->next; } } } if(a==nullptr) temp->next=b; else temp->next=a; return head->next; } } };
@takeUforward3 жыл бұрын
yes this works, this is the one used in merge of merge sort, good job!
@nitantjoshi99033 жыл бұрын
You can also do something like this. if(l1==null){ return l2; }else if(l2==null){ return l1; } ListNode head = new ListNode(); ListNode tail = head; while(l1!=null && l2 != null){ if(l1.val
@YASHDEWANGAN3 жыл бұрын
@@takeUforward could u tell the Time complexity of merge sort solution. I am confused between O(n log n) and O(n1 + n2)
@ritankarsarkar93943 жыл бұрын
@@YASHDEWANGAN in og merge sort, we do this comparison logn times(that's why nLogn). Here we are only doing it once, so complexity is O(n1 + n2)
@indhumathi5846 Жыл бұрын
understood :)
@harshdeepak32812 жыл бұрын
us!!
@vibhav_xiib_3529 Жыл бұрын
genta kuch samjh aayaa
@apporvaarya4 жыл бұрын
Knew it already
@aakashyadav62283 жыл бұрын
then fuck off
@VivekSharma-yl9ki4 жыл бұрын
Algoexpert charge 9k and you charge 33k , Is it sounds good. Do research and fix price then only your course is going to be sold.
U could had returned L1 and l2 u did in the end of recursive function..in the first else if condition only....why to create different if else and do so
@AnushaKondru-yl6uk11 ай бұрын
SinglyLinkedListNode* mergeLists(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) { SinglyLinkedListNode *dummy = new SinglyLinkedListNode(0); SinglyLinkedListNode *res = dummy; while(head1!=NULL&&head2!=NULL) { if(head1->data < head2->data) { SinglyLinkedListNode *node = head1; head1 = head1->next; res->next = node; res = node;; } else if(head2->data < head1->data) { SinglyLinkedListNode *node = head2; head2 = head2->next; res->next = node; res =node; } else { SinglyLinkedListNode *node = head2; head2 = head2->next; res->next = node; res =node; SinglyLinkedListNode *node2 = head1; head1= head1->next; res->next = node2; res = node2; } } while(head1!=NULL) { SinglyLinkedListNode *node = head1; head1 = head1->next; res->next = node; res =node; } while(head2!=NULL) { SinglyLinkedListNode *node = head2; head2 = head2->next; res->next = node; res = node; } return dummy->next; } using extra space and creating a new list