grid47 Exploring patterns and algorithms
Nov 6, 2024
6 min read
Solution to LeetCode 2: Add Two Numbers Problem
You are given two linked lists representing two non-negative integers, where each node contains a single digit, and the digits are stored in reverse order. Your task is to add these two numbers and return the result as a linked list. You can assume that the input does not contain leading zeros except for the number 0 itself.
Problem
Approach
Steps
Complexity
Input: The input consists of two linked lists representing integers in reverse order.
Example: l1 = [1, 2, 3], l2 = [4, 5, 6]
Constraints:
• 1 <= number of nodes in each linked list <= 100
• 0 <= Node.val <= 9
• The lists represent valid non-negative integers without leading zeros, except for 0 itself.
Output: The output is a linked list representing the sum of the two input integers in reverse order.
Example: [5, 7, 9]
Constraints:
• The resulting linked list must maintain reverse order.
• Each node in the linked list must have a value between 0 and 9.
Goal: To compute the sum of two integers represented as linked lists in reverse order and return the result as a linked list.
Steps:
• Initialize a dummy node to start the result linked list.
• Iterate through the two input linked lists while maintaining a carry for digit sums exceeding 9.
• Add corresponding digits from both lists along with the carry to calculate the sum.
• Create a new node for the result of each addition and append it to the result linked list.
• Continue until both lists are traversed and there is no carry left.
• Return the result linked list starting from the node next to the dummy.
Goal: Conditions that the input will always meet.
Steps:
• The input lists represent integers stored in reverse order.
• The result does not have leading zeros unless the number is 0.
Assumptions:
• The input is always valid.
• Both linked lists represent non-negative integers.
• Input: l1 = [3, 4, 2], l2 = [4, 6, 5]
• Explanation: The numbers represented are 243 and 564. Their sum is 807, so the output is [7, 0, 8].
• Input: l1 = [0], l2 = [0]
• Explanation: The numbers represented are 0 and 0. Their sum is 0, so the output is [0].
• Input: l1 = [9, 9, 9], l2 = [1]
• Explanation: The numbers represented are 999 and 1. Their sum is 1000, so the output is [0, 0, 0, 1].
Approach: We iterate through the linked lists while maintaining a carry to handle sums that exceed a single digit.
Observations:
• The reverse order of digits simplifies addition as we can process from least significant to most significant digit.
• A carry must be handled to account for sums greater than 9.
• Iterating through both linked lists while summing corresponding nodes and keeping track of the carry will give the desired result.
Steps:
• Create a dummy node to simplify result list creation.
• Initialize pointers for both linked lists and a variable for the carry.
• Iterate through both lists, summing corresponding digits and the carry.
• Calculate the new digit and update the carry.
• Create a new node for the digit and link it to the result list.
• Advance the pointers of the input lists if not null.
• Handle any remaining carry by creating an additional node if needed.
• Return the result list starting from the dummy's next node.
Empty Inputs:
• The input will always have at least one node per list.
Large Inputs:
• Handles linked lists with up to 100 nodes efficiently.
Special Values:
• Handles cases with all zeroes or where the carry extends the list.
Constraints:
• Handles sums resulting in longer linked lists than either input.
ListNode*addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* head =new ListNode(0);
ListNode* tail = head;
int rm =0;
while (l1 !=NULL|| l2 !=NULL|| rm !=0) {
int no1 = (l1 !=NULL) ? l1->val : 0;
int no2 = (l2 !=NULL) ? l2->val : 0;
int sum = no1 + no2 + rm;
int digit = sum %10;
rm = sum /10;
ListNode* nxt =new ListNode(digit);
tail->next = nxt;
tail = tail->next;
l1 = (l1 !=NULL) ? l1->next : NULL;
l2 = (l2 !=NULL) ? l2->next : NULL;
}
ListNode* res = head->next;
delete head;
return res;
}
