Merge Two Sorted Lists | Microsoft | Yahoo | Amazon

[@takeUforward]

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

yessss

[@subhamengine1143]

just watched the first 3 min and tried myself..and it was a successful submission.

[@PrinceKumar-el7ob]

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;

[@rohansinha2760]

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-oe6jo]

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-el7ob]

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;

[@SaumyaSharma007]

@@PrinceKumar-el7ob thanks bro i have coded with the same approch

[@amitarya4894]

@@PrinceKumar-el7ob same here bro

[@happy_soul184]

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

[@coding6409]

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

[@premanshdewangan8695]

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.

[@settyruthvik6236]

#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

[@mukeshbalaji04]

"Thissss iss the moment".... 😎😎

[@shreyapaul7257]

Probably the best explaination I have seen on the internet so far !!!

[@juhisingh4509]

One of the best Explanation. Your way of explaining concept is amazing. You are my motivation.

[@arjeriaharsh1]

In Java code, just add null check for the swap after the inner while loop.

[@hrithikrudra4292]

Bhaiya, please complete the DSA sheet fast..🙏🙏🙏

[@infinioda108]

Without interchanging the l1 & l2 too, we can easily do this.

[@adityaajay29]

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; }

[@NagaVijayKumar]

Thank you bro.. For uploading multiple videos in a single day..

[@bhavyaaggarwal8558]

This solution is also correct ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if(l1==NULL) return l2; if(l2==NULL) return l1; if(l1->valval) { l1->next= mergeTwoLists(l1->next,l2); return l1; } else { l2->next=mergeTwoLists(l1,l2->next); return l2; } }

[@takeUforward]

Yes it is correct, its much simpler and easy !

[@mananvarma5944]

Yes but you're using recursion which uses stack, so the space complexity would be O(n).

[@ranasauravsingh]

UNDERSTOOD... !!! Thanks striver for the video... :)

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

[@sayantaniguha8519]

This approach is just so much better and understandable

[@prakharsankrityayan1300]

Shouldn't the time complexity for the first approach be O(min(n1,n2))?

[@ankitkumaryadav562]

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

[@travelnlearn]

You made dsa easier and fun2 learn Thank You sir Love you may gbu with lots of succcess happiness love health and peace

[@baljotsinghchoudhary7434]

very complex solution simply use the logic of merge in merge sort

[@baljotsinghchoudhary7434]

@@takeUforward its constant space ListNode *tail = &dummy; while (l1 && l2) { if (l1->val < l2->val) { tail->next = l1; l1 = l1->next;} else { tail->next = l2; l2 = l2->next; } tail = tail->next; } tail->next = l1 ? l1 : l2; return dummy.next; }

[@takeUforward]

Yeah this also works fine.

[@coding6409]

@@baljotsinghchoudhary7434 This is O(n) space solution which he told before! He optimized it bro

[@ragnarT3]

@@coding6409 nop dude watch some space complexity videos... It is constant space

[@ravipatiramya4185]

@@baljotsinghchoudhary7434 can u give brute Force approach

[@Rohit_IITBHU]

solution with using dummy node has space complexity is O(1) You have told it in new video I m confused now

[@arjunkhanna1803]

The recursive code to sort in place is much easier

[@992_anisharoy9]

Thank you for such a wholesome explanation.

[@vikramjha4]

The best thing this guy is doing honestly apart from his awesome explanation is that he is not giving away the code! Respect++;

[@SatyamKumar-bw4vi]

wah Jhaji!

[@adi5962]

Chat gpt pe mil jayega code ab

[@parshantshukla4918]

No words to say what a nice explanation 😃🙏

[@avinash-xh6qw]

how does the swap function work over here? @take U forward

[@shikharsrivastava7312]

best explanation. tc of the first approach will only be o(length of smaller linked list)?

[@prakharsankrityayan1300]

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.

[@namansharma5128]

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.

[@rishabhkesarwani5761]

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

[@mayuprsv8990]

He trying to explain inplace solution and your will have additional space complexity which he already explain first part of video

[@namansharma5128]

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

[@namansharma5128]

I also thought the same way, idk why has he made it so complicated.

[@mohammadthousif3869]

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

[@DroidHolicOfficial]

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

[@vakhariyajay2224]

Thank you very much. You are a genius.

[@aakashyadav6228]

Bhai please complete the series. I have my placement in next 2 months and it all depends on you now. Please Please Please.

[@sathishkumar-dc9ce]

which clg bro?

[@tanishqua391]

why did we create a dummy node in the first approach ..we could've just moved duplicate dummy across our linked list?

[@rahul5913]

#behtreen explanation

[@cenacr007]

tbh using the same logic as merging sorted array would be better, swap is too much complicated I guess.

[@amitghosh4548]

What if I use recursion approach without using any external space instead of iterative way?

[@takeUforward]

recursion uses stack space

[@EverythingFootball0311]

@@takeUforward no we can do it without space using recursion

[@ng3w462]

@@EverythingFootball0311 how though?

[@masterroyjones4228]

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

[@praptiluthra163]

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

[@indonews8203]

the best way to understand any topic..

[@anubansal2462]

Shouldn't be the time complexity as min(l1, l2) ?

[@Mutant23]

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

[@newgamers439]

Thanks for the precise concept.

[@rohithbharathi3664]

U are explanation is very good but one thing please don't shout at me 😂

[@tauhait]

Simply superb!!

[@adarshbhardwaj6190]

Did someone noticed An Academy in the videos time stamps😂😂😂😂

[@kaichang8186]

understood, thanks for the great explanation

[@mmbmmbmmb]

DSA is soo complicated i cry everyday

[@shreyasingh7833]

Thanks for such a clear explnation..

[@PinaColada65]

this video is very helpful to me..thnks

[@kapilpatel9379]

When we do swap, doesn't that get counted as memory usage?

[@okey1317]

i know how it works,, but cant visualize well, expecially the end conditions 😪😪😪

[@curs3m4rk]

Super video! I applauded for ₹40.00 👏

[@bloody9162]

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.

[@cenacr007]

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.

[@bloody9162]

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

[@satyamgupta6030]

ultimate explaination thanks alot striver

[@Adityadekhrahahai]

in leetcode it is showing Runtime error when this code is implemented , can u tell mewhat is the wrong thing in this code ?

[@rohankumar393]

if(l1==null) return l2; if(l2==null) return l1; if(l1.val > l2.val){ ListNode tmp = l1; l1=l2; l2=tmp; } ListNode head = l1; while(l1!=null && l2!=null){ ListNode temp = null; while(l1!=null && l1.val

[@prakash_reddy4]

Maybe this line, it was (l1.val

[@mmbmmbmmb]

thank you so much

[@sarahdaniel6862]

👏👏👏 Clearly understood

[@sauravjha552]

Can I get a code with extra space?

[@rohitbagade9182]

[2] [1] found cycle for this tc

[@disharastogi5609]

very nice approach!!

[@shashwatsingh8340]

Can someone share the java code4 for this explaination, i guess the one in video has some issue

[@ajml_hnter]

Inplace simpler to understand code, think of it in terms of merge algorithm of arrays ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode* head = new ListNode(); // Dummy node ListNode* temp = head; while (list1 != NULL && list2 != NULL) { if (list1->val < list2->val) { temp->next = list1; list1 = list1->next; } else { temp->next = list2; list2 = list2->next; } temp = temp->next; } while (list1 != NULL) { temp->next = list1; list1 = list1->next; temp = temp->next; } while (list2 != NULL) { temp->next = list2; list2 = list2->next; temp = temp->next; } return head->next; // Skip the dummy node }

[@savalalingeshreddy6750]

i tried it myself and i finally got this solution Node* mergeLinkedList(Node* &h1,Node* &h2){ Node *temp = NULL; Node *dup = NULL; if(h1->data data){ temp = h1->next; } else{ dup = h1; h1 = h2; h2 = dup; temp = h1->next; } dup = h1; while(h2 != NULL && temp != NULL){ if(temp->data < h2->data){ h1->next = temp; h1 = h1->next; temp = temp->next; } else if(h2->data data){ h1->next = h2; h2 = h2->next; h1 = h1->next; } else{ h1->next = temp; h1 = h1->next; temp = temp->next; } } while(temp != NULL){ h1->next = temp; h1 = h1->next; temp = temp->next; } while(h2 != NULL){ h1->next = h2; h1 = h1->next; h2 = h2->next; } return dup; }

[@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; }

[@16avikasgupta70]

Thanks buddy for your help

[@indra16]

out standing

[@Dsa_withjay]

mind blowing !! bhayi really maza agyaa...!🥵

[@shashankgsharma0901]

Understood!

[@satya1067]

❤️❤️❤️❤️❤️❤️

[@aayushsharma9817]

great explanation

[@yashsingh9882]

Can someone please provide the java solution for the first algo that used external space?

[@devpant7829]

Priya mujhe pata hai tumhara linked list weak the... I still miss you priya please unblock😣

[@mehak_mits]

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; } };

[@roliverma5851]

Amazing!

[@mmbmmbmmb]

understood

[@m4n0jkum4r]

This code doesn't consider the duplicate elements.

[@udaykiransugali1139]

Great sir

[@lakshmiprasanna7058]

Understood 💯💯💯

[@arunsuthar4783]

in javascript

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

[@om_1_2]

Thanks broo👍👍👍

[@hmh7028]

You have complicated this question too much

[@indhumathi5846]

understood :)

[@naman_goyal]

Nice Bruh

[@shailypatel585]

nice video

[@largemars1642]

Sir aap Hindi me classes kariye na

[@takeUforward]

Community post pdho

[@abhirajtyagi9244]

👌👌👌🔥

[@harshdeepak3281]

us!!

[@uttamchandraketu2816]

You made too complicated in both approaches

[@ankitkumaryadav562]

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; }

[@mahipalsingh-yo4jt]

niceeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee

[@chirag_ccp]

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 ?

[@aayush5474]

copy of pointer is being passed. Pass a pointer to a pointer to make it work

[@adis6867]

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.

[@vibhav_xiib_3529]

genta kuch samjh aayaa

[@supratimbhattacharjee5324]

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; } } };

[@takeUforward]

yes this works, this is the one used in merge of merge sort, good job!

[@nitantjoshi9903]

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

[@YASHDEWANGAN]

@@takeUforward could u tell the Time complexity of merge sort solution. I am confused between O(n log n) and O(n1 + n2)

[@ritankarsarkar9394]

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

[@apporvaarya]

Knew it already

[@aakashyadav6228]

then fuck off

[@VivekSharma-yl9ki]

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.

[@takeUforward]

M not charging XD

[@saileshsirari2014]

public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode curr = dummy; while(l1 != null && l2!= null){ if(l1.val

[@sakshamsengar9798]

RECURSION:-- ListNode* f( ListNode* l1, ListNode* l2){ if(l1==NULL)return l2; if(l2==NULL)return l1; ListNode*h1 = l1; ListNode*h2 = l2; if(h1->valval){ h1->next = f(h1->next,h2); } else{ h2->next = f( h1,h2->next); } if(l1->valval)return l1; return l2; } ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if(l1==NULL)return l2; if(l2==NULL)return l1; return f(l1,l2); }

[@messi_codes]

good code

[@manistrikes]

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-yl6uk]

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