L5. Add 2 numbers in LinkedList | Dummy Node Approach

[@codeguy21]

you have already made a video on this , but still you upload a new lecture shows your dedication , like seriously hats-off brother

[@takeUforward]

Previous videos were for advanced people, in this, we are going slow, and we have the face cam too.

[@codeguy21]

@@takeUforward

[@sirajshaikh6959]

​@@takeUforwardBhai Strings ka playlist bana do plzz🙏🙏

[@shreyxnsh.14]

@@takeUforward yes strings please

[@kushalkollu8628]

@@takeUforward petition for striver ka heaps playlist

[@hashcodez757]

Man seriously!! just look at the views and the likes... Likes are not even 5% of the views. He is doing a lot of efforts for us ....kindly make sure that he is motivated equally... Go and hit the like button

[@RajNamdev_19]

I always do it

[@core_adii7333]

He just make DSA look easy

[@abhinavprabhat4418]

LC -2 class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { // Create a dummy node to simplify code and avoid special cases ListNode* dummynode = new ListNode(-1); // Pointer 'curr' is used to traverse and build the result linked list ListNode* curr = dummynode; // Pointers to traverse the input linked lists 'l1' and 'l2' ListNode* temp1 = l1; ListNode* temp2 = l2; // Variable to store the carry when adding digits int carry = 0; // Loop until both linked lists are exhausted while (temp1 != nullptr || temp2 != nullptr) { // Initialize 'sum' with the carry from the previous iteration int sum = carry; // If there are remaining digits in 'l1', add the digit to 'sum' if (temp1) sum += temp1->val; // If there are remaining digits in 'l2', add the digit to 'sum' if (temp2) sum += temp2->val; // Create a new node with the value being the last digit of 'sum' ListNode* newNode = new ListNode(sum % 10); // Update 'carry' with the tens digit of 'sum' carry = sum / 10; // Link the new node to the result linked list curr->next = newNode; // Move 'curr' to the newly added node curr = curr->next; // Move pointers to the next nodes in 'l1' and 'l2' if there are remaining nodes if (temp1) temp1 = temp1->next; if (temp2) temp2 = temp2->next; } // If there is a remaining carry after the loop, create a new node with the carry if (carry) { ListNode* newNode = new ListNode(carry); curr->next = newNode; } // Return the head of the result linked list (next of the dummy node) return dummynode->next; } };

[@AmanSharma-xy1qm]

All the video lectures and the articles helped me a lot to gain confidence in DSA and will be helping me in the interviews. Thank you Striver bhaiya for bringing such amazing content for free.

[@charansaianisetti5436]

HI striver, with the basics and fundamentals that you taught us, i am able to solve this question inplace - even without creating a single node ( but the time compelxity is O(2N+2M) ) thank you so much for the amazing playlist

[@AshishSingh-he2qo]

We can store the results in any one list head and can create new node if require which decreases space complexity ❤❤

[@AshishSingh-he2qo]

Below is code ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { if(l1==NULL && l2==NULL) return NULL; if(l1==NULL) return l2; if(l2==NULL) return l1; ListNode* t1 = l1; ListNode* t2 = l2; ListNode* p1 = NULL; ListNode* p2 = NULL; int c=0; while(t1!=NULL && t2!=NULL){ t1->val=t1->val+t2->val+c; if(t1->val>=10){ int r = t1->val%10; c=t1->val/10; t1->val=r; } else{ c=0; } p1=t1; p2=t2; t1=t1->next; t2=t2->next; } if(t1!=NULL && c==0){ return l1; } if(t2!=NULL && c==0){ p1->next=t2; return l1; } while(t1!=NULL && c){ t1->val+=c; if(t1->val>=10){ int r = t1->val%10; c = t1->val/10; t1->val=r; } else{ c=0; } p1=t1; t1=t1->next; } if(t1==NULL && c && t2==NULL){ ListNode* nl =new ListNode(c); p1->next=nl; return l1; } if(t1==NULL && c==0) return l1; if(t2!=NULL && c){ p1->next=t2; while(t2!=NULL && c){ t2->val+=c; if(t2->val>=10){ int r = t2->val%10; c = t2->val/10; t2->val=r; } else{ c=0; } p2=t2; t2=t2->next; } } if(t2==NULL && c){ ListNode* nl= new ListNode(c); p2->next=nl; return l1; } if(t2==NULL && c==0) return l1; return l1; }

[@gup_ayush]

there is a optimal approach also of O(max(m,n)) (tc) and O(1) (sc)

[@sajalprajapati6397]

We can definitely optimize this code. If we have two linked lists of unequal length, we can use the longer linked list, helping us reduce the space complexity to O(1). By the way, thank you, Striver Bhaiya. You really help me in improving my logic. This logic is derived from your three approaches viewpoint. It’s really helpful, man! I hope I secure a placement soon. 😁😁😁😁😁

[@saurabhtamta7295]

Can you give the code for this? Won't we need one more traversal to find out which is longer?

[@synk__47]

Hey how will it be O(1)????

[@ahmadentertainmentshorts4222]

Thank you for creating such a great content for free 🎉❤

[@harshit.53]

I had written the code for this myself but you showed proper way to reduce the number of lines of code, instead of my 3 while loop implementation it reduced to one loop

[@3idiots-iiitdmjabalpur]

We should, Store the dummyHead in temp, Then do dummyHead->next, temp->next = nullptr; delete temp; return dummyHead

[@BalakrishnaPerala]

instead we could also use these, Node head = dummyHead.next; dummyHead.next = null; delete dummyHead; return head;

[@DeveshSoni-u6s]

i thought i wrote a good code. Apparently this was WAYYYYYY shorter thanks to the guy. DUMMY APPROACH was great too

[@PiyushKumar-xe1ng]

we can optimize the space complexity O(1) by modifying the data in the given lists (l1->data=l1->data+l2->data+carry) and if l1 is shorter than l2 we can point l1->next=l2->next ListNode* addTwoNumbers(ListNode* link1, ListNode* link2) { ListNode*l1=link1; ListNode*l2=link2; ListNode*temp; if(!l1 && !l2)return nullptr; if(!l1 && l2)return l2; if(l1 && !l2)return l1; int carry=0; while(l1 &&l2){ l1->val=l1->val+l2->val+carry; carry=0; if(l1->val>=10){ carry=l1->val/10; l1->val=l1->val%10; } if(l1->next==nullptr &&l2->next){ l1->next=l2->next; l1=l1->next; break; } temp=l1; l1=l1->next; l2=l2->next; } while(l1){ l1->val=l1->val+carry; carry=0; if(l1->val>=10){ carry=l1->val/10; l1->val=l1->val%10; } temp=l1; l1=l1->next; } if(!l1 &&carry>0){ ListNode*newnode=new ListNode(carry); temp->next=newnode; } return link1;

[@harshitgarg2820]

completed the video, having a great fun solving these problems🚀🚀

[@Fun__Facts-d2y]

in above question space complexity can be of O(1) ...when result is stored in linked list having maximum length among two given linked list

[@kushiksahu1983]

how will you determine whether which one is having max length initially. for determining the max len we have to run an extra O(n) loop. Am i right, if not please correct me.

[@Fun__Facts-d2y]

@@kushiksahu1983 i am considering space complexity not time complexity

[@ShivamUchiha]

nice explanation

[@SHIVAMSHIVAM-w4k]

Quite simple and Amazing approach.thank you bhaiya for such amazing explanation

[@anushasingh5562]

Didn't understood need to make dummy node ...why cant we simply made head , store sum in it and return

[@gokulanvs]

It's not a big deal,just for the convenient if you simply made a head node without dummy you have to create all the stuff like getting the values from the list and sum and carry a value outside the loop also, but if you made dummy head you write this code only once inside the loop

[@suprith5443]

If u create dummy node u can get head easily just by returning dummy->next

[@riyasinghal7185]

You can do that without dummy node as well.. in that case you will assign the head to Null... You will have to add extra code to check if head null for the first time then assign this value else add to it's next ... To avoid that you simply assign a dummy value to the head and always add to it's next ...

[@arnav7050]

class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* temp1 = l1; ListNode* temp2 = l2; int carry = 0; while (temp1 && temp2) { temp1->val = temp1->val + temp2->val + carry; if (temp1->val > 9) { temp1->val -= 10; carry = 1; } else { carry = 0; } temp1 = temp1->next; temp2 = temp2->next; } if (!temp1) { ListNode *gadha = temp1; temp1 = temp2; temp2 = gadha; ListNode* last = l1; while (last->next != nullptr) { last = last->next; } last->next = temp1; } while (temp1 && carry == 1) { temp1->val = temp1->val + carry; if (temp1->val > 9) { temp1->val -= 10; carry = 1; } else carry = 0; temp1 = temp1->next; } if (carry == 1) { ListNode* lastNode = l1; while (lastNode->next != nullptr) { lastNode = lastNode->next; } ListNode* ne = new ListNode(1); lastNode->next = ne; } return l1; } }; i tried to do it in O(1) space by changing the first list only Is my space complexity analysis correct?

[@yourhonestbro217]

yes it is correct here is my code for the same static ListNode add(ListNode l1, ListNode l2) { int carry = 0; ListNode temp1 = l1; ListNode temp2 = l2; ListNode prev = null; while (temp1 != null || temp2 != null) { int sum = carry; if(temp1 != null) sum += temp1.val; if(temp2 != null) sum += temp2.val; int val = sum%10; carry = sum/10; if(temp1 != null){ temp1.val = val; prev = temp1; temp1 = temp1.next; } else if(temp2 != null){ temp2.val = val; prev.next = temp2; prev = temp2; } if(temp2 != null) temp2 = temp2.next; } if(carry == 1){ ListNode n = new ListNode(1); prev.next = n; } return l1; }

[@yashwanthyerra2820]

@@yourhonestbro217 there is one error in this what if temp1 is null at beginning then it will go to else if part and you are taking prev.next which means you are accessing null's next which raises null pointer exception

[@yashwanthyerra2820]

​@@yourhonestbro217 class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode t1 = l1,t2 =l2,dNode = new ListNode(-1),prev = dNode; int carry = 0; while(t1!=null || t2 !=null){ int sum = carry; if(t1!=null) sum+=t1.val; if(t2!=null) sum+=t2.val; int val = sum%10; carry = sum/10; if(t1!=null){ t1.val = val; prev.next = t1; prev = t1; t1 = t1.next; } else if(t2!=null){ t2.val = val; prev.next = t2; prev = t2; } if(t2!=null)t2 = t2.next; } if(carry!=0){ ListNode n = new ListNode(carry); prev.next = n; } return dNode.next; } } take dummynode instead of null that will help you

[@shantanugupta-oz1dx]

I never thought in terms of sum%10 and carry=sum/10. Thank you so much for explaining it so well

[@chetashreejagtap7585]

thank you striver, nice explanation👍

[@VinitSoul]

God of dsa🎉🎉🎉🙌

[@naseemsiddiqui154]

we can use existing node in place of new node.

[@nishant4595]

was able to solve this !!!! feeling a lil good

[@ArnabBhadra02]

i have a doubt im 33 and 34 line, when both temp1 and temp 2 is not null, then sum will be added twice means carry will be added twice, if i am wrong please correct me

[@Jashu-er7gs]

Yes u r right. I think adding this one can help! Sum=carry; If(t1 && t2) { Sum=sum+t1.val+t2.val; }

[@soumikchakrabarty8077]

dada there is no link of solution in the description.

[@ankitashah4295]

u r really amazing bro

[@prasanjit.bhanja]

DSA God ❤

[@harshinikanagarla4401]

if we store the sum in linked list1 itself then we can reduce space complexity right!!

[@sheepcode__]

But, it is not a good practice for interviews to tamper the input!

[@sheeladevi1640]

UNDERSTOOD

[@anshusorrot316]

I have completed this ques without taking new list by storing result in list of max size

[@yourhonestbro217]

you don't need to find the max list you can just relink the list1 is last node if list 2 is longer here is the code static ListNode add(ListNode l1, ListNode l2) { int carry = 0; ListNode temp1 = l1; ListNode temp2 = l2; ListNode prev = null; while (temp1 != null || temp2 != null) { int sum = carry; if(temp1 != null) sum += temp1.val; if(temp2 != null) sum += temp2.val; int val = sum%10; carry = sum/10; if(temp1 != null){ temp1.val = val; prev = temp1; temp1 = temp1.next; } else if(temp2 != null){ temp2.val = val; prev.next = temp2; prev = temp2; } if(temp2 != null) temp2 = temp2.next; } if(carry == 1){ ListNode n = new ListNode(1); prev.next = n; } return l1; }

[@NazeerBashaShaik]

Understood, thank you.

[@ankush8243]

Thank you very much!🥰💙

[@Mel-up7un]

Understood!!

[@codamer6933]

in the while loop we have to use || else && ? for suppose if we have 2 nodes in the first head and 4 nodes in the second head atm we are not going to check for other nodes which are present in the second head? can anyone explain me pls,what do we use either || else &&?

[@DeadPoolx1712]

UNDERSTOOD;

[@abhisekparida2682]

striver bhai lauch django playlist please !!!!

[@LuckyKumar-mt9km]

I have solved this question in O(1) space as in leetcode, there was nothing mentioned to make new list, I have just added two lists and stored the result in place of longer list, Is it good approach ? ListNode* add(ListNode* t1, ListNode* t2) { ListNode* temp1 = t1; ListNode* temp2 = t2; ListNode* prev2 = NULL; int carry =0; while(temp1) { int sum = temp1->val + temp2->val + carry; if(sum >= 10) { int rem = sum %10; carry =1; temp2->val = rem; } else{ carry=0; temp2->val = sum; } temp1 = temp1->next; prev2 = temp2; temp2 = temp2->next; } while(carry == 1) { if(temp2 == NULL) { ListNode* newNode = new ListNode(1); prev2->next = newNode; carry = 0; } else{ int sum = temp2->val + carry; if(sum >= 10) { int rem = sum %10; carry =1; temp2->val = rem; } else{ carry=0; temp2->val = sum; } prev2 = temp2; temp2 = temp2->next; } } return t2; } ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* temp1 = l1; ListNode* temp2 = l2; int count1 = 0; int count2=0; while(temp1) { count1++; temp1 = temp1->next; } while(temp2) { count2++; temp2 = temp2 -> next; } if(count1< count2) { return add(l1,l2); } else{ return add(l2,l1); } }

[@LuseBiswas]

Bro can you provide me your solved LeetCode link, because it such an eye opener code from me, but somehow, 1 testcase is not passed

[@jeethora586]

@@LuseBiswas bro what if carry is more than 1

[@invinciblegaming32]

Same i also soloved the same way

[@YourCodeVerse]

Understood✅🔥🔥

[@nayankhuman1043]

Understood :)

[@oyeesharme]

thanks bhaiya

[@pushkarwaykole7043]

If the given linked list is not in reversed order ,than is there any way to solve it without reversing the list?

[@yourhonestbro217]

recursion but the call stack would be counted as space complexity if the interviewer allowed you to overwrite the input linked list then you can do this question in constant space instead of max(m,n)

[@pushkarwaykole7043]

@@yourhonestbro217 The issue is not with space complexity, the interviewer asked me to optimize the space complexity.I was asking for any more time efficient approach

[@yourhonestbro217]

@@pushkarwaykole7043 the best time complexity can be O(max(m,n)) in any scenario nothing better than that in this question.

[@rushidesai2836]

Striver you gem, thanks for your efforts!

[@rahulmandal4007]

Thank you

[@NARUTOUZUMAKI-bk4nx]

Understoood

[@ShreevatsaN-ro4ry]

What is sum from t1 and t2 comes to be at 100 for example, then carry would be 100/10 ie 10, so how can we just add 10 to next node as the last step, shouldnt it be 1 and then 0?

[@Sandeep-tn8mz]

Bro, every iteratin you will be adding two numbers which are less than 10..

[@deadlock4919]

Thank you 🫂

[@tushar7305]

like we did in merge two sorted LinkedList can not we store the answer in anyone LinkedList and optimised the space ?

[@AyushMishra-b8w]

Avoid changing initial data given in most of the cases. In merge sort we wanted same array to be sorted

[@Dont_know_wt]

Thanks

[@RituSingh-ne1mk]

Understood!

[@ganeshvhatkar9253]

Understood

[@i2_34_priyankkumarsingh8]

Can anyone explain why are we using || and not && in the while loop got confused there?

[@gladiator8316]

Bro u got the answer?

[@sonakshibajpai6445]

understood!

[@riteshraj64]

💞💞

[@robot3.077]

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { if(l1==NULL&&l2==NULL){ return NULL; } ListNode* t1=l1; ListNode* t2=l2; ListNode* dummy=new ListNode(-1); ListNode*current=dummy; int sum,carry=0; while(t1!=NULL&&t2!=NULL){ sum=(t1->val+t2->val+carry)%10; carry=(t1->val+t2->val+carry)/10; ListNode* newnode=new ListNode(sum); current->next=newnode; current=newnode; t1=t1->next; t2=t2->next; } while(t1!=NULL){ sum=(t1->val+carry)%10; carry=(t1->val+carry)/10; ListNode* newnode=new ListNode(sum); current->next=newnode; current=newnode; t1=t1->next; } while(t2!=NULL){ sum=(t2->val+carry)%10; carry=(t2->val+carry)/10; ListNode* newnode=new ListNode(sum); current->next=newnode; current=newnode; t2=t2->next; } if(carry){ ListNode* newnode=new ListNode(carry); current->next=newnode; current=newnode; } return dummy->next; } };

[@shaiksoofi3741]

thx

[@vaibhavthalanki7320]

we can do it in-place but the code gets messy

[@yourhonestbro217]

ya a bit but not much here is the in place code static ListNode add(ListNode l1, ListNode l2) { int carry = 0; ListNode temp1 = l1; ListNode temp2 = l2; ListNode prev = null; while (temp1 != null || temp2 != null) { int sum = carry; if(temp1 != null) sum += temp1.val; if(temp2 != null) sum += temp2.val; int val = sum%10; carry = sum/10; if(temp1 != null){ temp1.val = val; prev = temp1; temp1 = temp1.next; } else if(temp2 != null){ temp2.val = val; prev.next = temp2; prev = temp2; } if(temp2 != null) temp2 = temp2.next; } if(carry == 1){ ListNode n = new ListNode(1); prev.next = n; } return l1; }

[@sparshverma4030]

understood

[@harshuke5831]

Understood 30lakh

[@topg-fg5fu]

love

[@Mihir_Jain]

upload string

[@harshitjaiswal9439]

🔥🔥🔥

[@hardikpatel352]

understood;)

[@gautamsaxena4647]

understood bhaiya

[@YashGaneriwal-je6rh]

done

[@srajangarg21]

Node newNode = new Node(sum%10); i have doubt in this line

[@rahulmandal4007]

If you have doubt in this basics then go back and do basics programs its not for u

[@kritwaneditz9006]

LORD

[@AkashKumarTiwary-u4b]

God

[@Chanch880]

❤

[@web_resource]

6:23

[@LochanSaroy]

First comment😍

[@cenacr007]

us

[@Sahilsharma-sk5vr]

100th comment

[@printfiamd5254]

Is this correct??? Node *Sum(Node *head1, Node *head2) { if (head1 == NULL && head2 == NULL) return NULL; Node *ptr1 = head1; Node *ptr2 = head2; Node *dummy = new Node(-1); Node *curr = dummy; int val = 0, carry = 0; while (ptr1 != NULL && ptr2 != NULL) { val = carry + ptr1->data + ptr2->data; carry = val / 10; val %= 10; ptr1 = ptr1->next; ptr2 = ptr2->next; curr->next = new Node(val); curr = curr->next; } while (ptr1 != NULL) { val = carry + ptr1->data; carry = val / 10; val %= 10; curr->next = new Node(val); curr = curr->next; ptr1 = ptr1->next; } while (ptr2 != NULL) { val = carry + ptr2->data; carry = val / 10; val %= 10; curr->next = new Node(val); curr = curr->next; ptr2 = ptr2->next; } if (carry) { curr->next = new Node(carry); curr = curr->next; } Node *head = dummy->next; return head; }

[@ankitsharda1131]

yes I did same too...TC will be same for this code too as striver's...but his code is much cleaner and readable.

[@aashwinkumar2242]

there were lots and lots of errors

[@rajatshukla2605]

understood!

[@subee128]

Thanks

[@codeman3828]

Understood

[@firebout7675]

understood

[@dhruvsovasaria]

thankyou

[@pradipkumarmukhi]

Understood

[@chiragbansod8252]

understood

[@dewanandkumar8589]

Understood

[@abhinanda7049]

understood

[@adityapandey23]

Understood

[@ashishpradhan6250]

understood

[@rahulmandal4007]

Pradhan shab kaisan ba

[@MJBZG]

understood

[@himanshidafouty347]

Understood

[@rahulmandal4007]

What do you understood care to explain?

[@rutujashelke4208]

Understood

[@abhinavabhi3568]

Understood

[@satyanarayanbarik1701]

Understood