Add Two Numbers Leetcode Solution
Add Two Numbers Leetcode Problem :
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Add Two Numbers Leetcode Solution :
Constraints :
- The number of nodes in each linked list is in the range [1, 100].
- 0 <= Node.val <= 9
- It is guaranteed that the list represents a number that does not have leading zeros
Example 1:
Input: l1 = [0], l2 = [0]Output: [0]
Example 2:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]Output: [8,9,9,9,0,0,0,1]
Intuition:
The Intuition is to iterate through two linked lists representing non-negative integers in reverse order, starting from the least significant digit. It performs digit-wise addition along with a carry value and constructs a new linked list to represent the sum. The process continues until both input lists and the carry value are exhausted. The resulting linked list represents the sum of the input numbers in the correct order.
Explanation:
- Create a placeholder node called dummyHead with a value of 0. This node will hold the resulting linked list.
- Initialize a pointer called tail and set it to dummyHead. This pointer will keep track of the last node in the result list.
- Initialize a variable called carry to 0. This variable will store the carry value during addition.
- Start a loop that continues until there are no more digits in both input lists (l1 and l2) and there is no remaining carry value.
- Inside the loop:
- Check if there is a digit in the current node of
l1. If it exists, assign its value to a variable called digit1. Otherwise, set digit1 to 0. - Check if there is a digit in the current node of
l2. If it exists, assign its value to a variable called digit2. Otherwise, set digit2 to 0. - Add the current digits from l1 and
l2, along with the carry value from the previous iteration, and store the sum in a variable called sum. - Calculate the unit digit of sum by taking the modulus (%) of sum by 10. This digit will be placed in a new node for the result.
- Update the carry variable by dividing sum by 10 and taking the integer division part. This gives us the carry value for the next iteration.
- Create a new node with the calculated digit as its value.
- Attach the new node to the tail node of the result list.
- Move the tail pointer to the newly added node.
- Move to the next nodes in both l1 and l2, if they exist. If either list is exhausted, set the corresponding pointer to nullptr.
- Check if there is a digit in the current node of
- After the loop, obtain the actual result list by skipping the dummyHead node.
- Delete the dummyHead node.
- Return the resulting list.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* dummyHead = new ListNode(0);
ListNode* tail = dummyHead;
int carry = 0;
while (l1 != nullptr || l2 != nullptr || carry != 0) {
int digit1 = (l1 != nullptr) ? l1->val : 0;
int digit2 = (l2 != nullptr) ? l2->val : 0;
int sum = digit1 + digit2 + carry;
int digit = sum % 10;
carry = sum / 10;
ListNode* newNode = new ListNode(digit);
tail->next = newNode;
tail = tail->next;
l1 = (l1 != nullptr) ? l1->next : nullptr;
l2 = (l2 != nullptr) ? l2->next : nullptr;
}
ListNode* result = dummyHead->next;
delete dummyHead;
return result;
}
};
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0);
ListNode tail = dummyHead;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int digit1 = (l1 != null) ? l1.val : 0;
int digit2 = (l2 != null) ? l2.val : 0;
int sum = digit1 + digit2 + carry;
int digit = sum % 10;
carry = sum / 10;
ListNode newNode = new ListNode(digit);
tail.next = newNode;
tail = tail.next;
l1 = (l1 != null) ? l1.next : null;
l2 = (l2 != null) ? l2.next : null;
}
ListNode result = dummyHead.next;
dummyHead.next = null;
return result;
}
}
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
dummyHead = ListNode(0)
tail = dummyHead
carry = 0
while l1 is not None or l2 is not None or carry != 0:
digit1 = l1.val if l1 is not None else 0
digit2 = l2.val if l2 is not None else 0
sum = digit1 + digit2 + carry
digit = sum % 10
carry = sum // 10
newNode = ListNode(digit)
tail.next = newNode
tail = tail.next
l1 = l1.next if l1 is not None else None
l2 = l2.next if l2 is not None else None
result = dummyHead.next
dummyHead.next = None
return result
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment