L5. Add 2 numbers in LinkedList | Dummy Node Approach

Problem Link: tinyurl.com/5n98urdv
Entire LL Sheet: takeuforward.org/linked-list/...
Check our A2Z DSA Course: takeuforward.org/strivers-a2z...
Please do give us a like, and subscribe to us if you are new to our channel.
Do follow us on our socials: linktr.ee/takeuforward

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

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

[@ahmadentertainmentshorts4222]

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

[@harshitgarg2820]

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

[@user-vg4ld7rf3v]

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

[@rushidesai2836]

Striver you gem, thanks for your efforts!

[@chetashreejagtap7585]

thank you striver, nice explanation👍

[@core_adii7333]

He just make DSA look easy

[@NazeerBashaShaik]

Understood, thank you.

[@ankush8243]

Thank you very much!🥰💙

[@nothing-ce6rs]

Thanks

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

[@YourCodeVerse]

Understood✅🔥🔥

[@sonakshibajpai6445]

understood!

[@RituSingh-ne1mk]

Understood!

[@NARUTOUZUMAKI-bk4nx]

Understoood

[@deadlock4919]

Thank you 🫂

[@user-gb5id1nt8v]

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

[@sparshverma4030]

understood

[@adityapandey23]

Understood

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

[@riteshraj64]

💞💞

[@Chanch880]

❤

[@harshitjaiswal9439]

🔥🔥🔥

[@hardikpatel352]

understood;)

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

[@naseemsiddiqui154]

we can use existing node in place of new node.

[@Vijay-xk3ew]

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.

[@Vijay-xk3ew]

@@kushiksahu1983 i am considering space complexity not time complexity

[@soumikchakrabarty8077]

dada there is no link of solution in the description.

[@arnab_bhadra_0375]

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

[@LochanSaroy]

First comment😍

[@tushar7305]

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

[@user-oz2eu7rs8v]

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

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

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

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

[@harshuke5831]

Understood 30lakh

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

[@user-gk4zy6bk7l]

God

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

[@srajangarg21]

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

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

[@cenacr007]

us

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

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

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

[@subee128]

Thanks

[@dewanandkumar8589]

Understood

[@ashishpradhan6250]

understood

[@ganeshvhatkar9253]

Understood

[@himanshidafouty347]

Understood

[@codeman3828]

Understood

[@pradipkumarmukhi]

Understood

[@abhinanda7049]

understood

[@chiragbansod8252]

understood

[@firebout7675]

understood