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
Пікірлер: 100
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
you have already made a video on this , but still you upload a new lecture shows your dedication , like seriously hats-off brother
@takeUforward
8 ай бұрын
Previous videos were for advanced people, in this, we are going slow, and we have the face cam too.
@codeguy21
8 ай бұрын
@@takeUforward
@sirajshaikh6959
6 ай бұрын
@@takeUforwardBhai Strings ka playlist bana do plzz🙏🙏
@shreyxnsh.14
6 ай бұрын
@@takeUforward yes strings please
@kushalkollu8628
2 ай бұрын
@@takeUforward petition for striver ka heaps playlist
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
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.
Thank you for creating such a great content for free 🎉❤
He just make DSA look easy
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; } };
completed the video, having a great fun solving these problems🚀🚀
thank you striver, nice explanation👍
I never thought in terms of sum%10 and carry=sum/10. Thank you so much for explaining it so well
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. 😁😁😁😁😁
Thank you very much!🥰💙
Understood, thank you.
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
Understood✅🔥🔥
thanks bhaiya
i thought i wrote a good code. Apparently this was WAYYYYYY shorter thanks to the guy. DUMMY APPROACH was great too
Thanks
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;
Thank you 🫂
Understoood
We should, Store the dummyHead in temp, Then do dummyHead->next, temp->next = nullptr; delete temp; return dummyHead
@BalakrishnaPerala
2 ай бұрын
instead we could also use these, Node head = dummyHead.next; dummyHead.next = null; delete dummyHead; return head;
Quite simple and Amazing approach.thank you bhaiya for such amazing explanation
Understood!
Striver you gem, thanks for your efforts!
@rahulmandal4007
Ай бұрын
Thank you
God of dsa🎉🎉🎉🙌
understood!
understood
Understood
thx
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
2 ай бұрын
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
2 ай бұрын
@@kushiksahu1983 i am considering space complexity not time complexity
💞💞
understood;)
DSA God ❤
we can use existing node in place of new node.
🔥🔥🔥
Didn't understood need to make dummy node ...why cant we simply made head , store sum in it and return
@gokulanvs
6 ай бұрын
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
4 ай бұрын
If u create dummy node u can get head easily just by returning dummy->next
@riyasinghal7185
3 ай бұрын
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 ...
❤
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; }
dada there is no link of solution in the description.
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 &&?
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; }
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; }
Understood 30lakh
Can anyone explain why are we using || and not && in the while loop got confused there?
if we store the sum in linked list1 itself then we can reduce space complexity right!!
@sheepcode__
12 күн бұрын
But, it is not a good practice for interviews to tamper the input!
like we did in merge two sorted LinkedList can not we store the answer in anyone LinkedList and optimised the space ?
@user-oz2eu7rs8v
3 ай бұрын
Avoid changing initial data given in most of the cases. In merge sort we wanted same array to be sorted
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 { return add(l1,l2); } else{ return add(l2,l1); } }
@LuseBiswas
4 ай бұрын
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
2 ай бұрын
@@LuseBiswas bro what if carry is more than 1
@invinciblegaming32
Ай бұрын
Same i also soloved the same way
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
5 ай бұрын
Bro, every iteratin you will be adding two numbers which are less than 10..
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.
First comment😍
God
/** * 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; } };
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; }
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
us
100th comment
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
7 ай бұрын
yes I did same too...TC will be same for this code too as striver's...but his code is much cleaner and readable.
Thanks
Understood
understood
Understood
understood
understood
understood
Understood
Understood
Understood
@rahulmandal4007
Ай бұрын
What do you understood care to explain?
understood
@rahulmandal4007
Ай бұрын
Pradhan shab kaisan ba