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

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

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

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

[@ahmadentertainmentshorts4222]

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

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

[@Nikhil-jd2up]

you should not alter input data unless you are asked to

[@Shaik_1811]

Strings plz🙏

[@shwetachoudhary9003]

thank you soo much for ur each and every videoo❤🎉🎉

[@gup_ayush]

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

[@harshitgarg2820]

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

[@VinitSoul]

God of dsa🎉🎉🎉🙌

[@DeveshSoni-u6s]

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

[@chetashreejagtap7585]

thank you striver, nice explanation👍

[@ShivamUchiha]

nice explanation

[@momentcoder]

Understood 😀

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

[@ankitashah4295]

u r really amazing bro

[@PCCOERCoder]

Lecture successfully completed on 27/11/2024 🔥🔥

[@KotgireTejas]

what semester bro ?

[@ankush8243]

Thank you very much!🥰💙

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

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

[@rumiNITPatna]

thank u sir! done

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

[@nishant4595]

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

[@mainakdasgupta7130]

thank you man

[@YourCodeVerse]

Understood✅🔥🔥

[@NazeerBashaShaik]

Understood, thank you.

[@prasanjit.bhanja]

DSA God ❤

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

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

[@deadlock4919]

Thank you 🫂

[@soumikchakrabarty8077]

dada there is no link of solution in the description.

[@om3478]

understood!!!

[@oyeshxrme]

thanks bhaiya

[@riteshraj64]

💞💞

[@Dont_know_wt]

Thanks

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

[@sheeladevi1640]

UNDERSTOOD

[@Mel-up7un]

Understood!!

[@naseemsiddiqui154]

we can use existing node in place of new node.

[@DeadPoolx1712]

UNDERSTOOD;

[@shaiksoofi3741]

thx

[@heyRay81194]

can we solve this by taking larger list between l1 and l2 and store the result there without using an additional list

[@NARUTOUZUMAKI-bk4nx]

Understoood

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

[@sonakshibajpai6445]

understood!

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

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

[@ganeshvhatkar9253]

Understood

[@RituSingh-ne1mk]

Understood!

[@rushidesai2836]

Striver you gem, thanks for your efforts!

[@rahulmandal4007]

Thank you

[@harshitjaiswal9439]

🔥🔥🔥

[@sparshverma4030]

understood

[@nayankhuman1043]

Understood :)

[@shantanugupta-oz1dx]

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

[@abhisekparida2682]

striver bhai lauch django playlist please !!!!

[@SHIVAMSHIVAM-w4k]

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

[@YashGaneriwal-je6rh]

done

[@topg-fg5fu]

love

[@hardikpatel352]

understood;)

[@aayushnehra9813]

easy

[@Chanch880]

❤

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

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

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

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

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

[@web_resource]

6:23

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

[@Mihir_Jain]

upload string

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

[@OnelastFight-e7y]

[@harshuke5831]

Understood 30lakh

[@AkashKumarTiwary-u4b]

God

[@heyOrca2711]

Nov 26, 2024

[@kritwaneditz9006]

LORD

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

[@gautamsaxena4647]

understood bhaiya

[@cenacr007]

us

[@LochanSaroy]

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

[@Sahilsharma-sk5vr]

100th comment

[@aashwinkumar2242]

there were lots and lots of errors

[@santhoshl-zq1op]

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public int length(ListNode node){ ListNode temp = node; int cnt = 0; while(temp != null){ cnt++; temp = temp.next; } return cnt; } public ListNode addTwoNumbers(ListNode l1, ListNode l2) { int n = findMaxLength(l1, l2); int carry = 0; if(n > 0){ ListNode temp1 = l1; ListNode temp2 = l2; while(temp2 != null){ temp1.val = carry + temp1.val + temp2.val; if(temp1.val >= 10){ carry = temp1.val / 10; temp1.val = temp1.val % 10; } else { carry = 0; } temp2 = temp2.next; temp1 = temp1.next; } while(temp1 != null){ temp1.val = carry + temp1.val; if(temp1.val >= 10){ carry = temp1.val / 10; temp1.val = temp1.val % 10; } else { carry = 0; } temp1 = temp1.next; } if(carry == 0){ return l1; } ListNode newNode = new ListNode(carry); temp1 = l1; while(temp1.next != null){ temp1 = temp1.next; } temp1.next = newNode; return l1; }else{ ListNode temp1 = l1; ListNode temp2 = l2; while(temp1 != null){ temp2.val = carry + temp2.val + temp1.val; if(temp2.val >= 10){ carry = temp2.val / 10; temp2.val = temp2.val % 10; } else { carry = 0; } temp1 = temp1.next; temp2 = temp2.next; } while(temp2 != null){ temp2.val = carry + temp2.val; if(temp2.val >= 10){ carry = temp2.val / 10; temp2.val = temp2.val % 10; } else { carry = 0; } temp2 = temp2.next; } if(carry == 0){ return l2; } ListNode newNode = new ListNode(carry); temp2 = l2; while(temp2.next != null){ temp2 = temp2.next; } temp2.next = newNode; return l2; } } public int findMaxLength(ListNode l1, ListNode l2){ return length(l1) - length(l2); } } THis is my code where time complexity is O (max ( l1+ l2 )) but SC is o(1) i don't use any extra space

[@subee128]

Thanks

[@rajatshukla2605]

understood!

[@firebout7675]

understood

[@codeman3828]

Understood

[@dhruvsovasaria]

thankyou

[@chiragbansod8252]

understood

[@pradipkumarmukhi]

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?