Let's solve one of the most famous leetcode questions today which is about adding two numbers in a linked list.
Analyzing Add Two Numbers" 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.
Example 1:
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
Understanding the Problem
Before diving into the code, let's break down the problem and understand what's expected:
You're given two linked lists,
l1
andl2
, where each node contains a digit.The digits are stored in reverse order. That means the 1's digit is at the head of the list, followed by the 10's digit, and so on.
Your task is to add these two numbers and return the result as a linked list.
The Approach
To solve this problem, we can use a simple iterative approach that resembles how we manually add numbers. Here's the intuition behind the approach:
Initialize Variables: We start by initializing some variables. We'll maintain two pointers,
temp1
andtemp2
, to traversel1
andl2
, respectively. We also initialize acarry
variable to handle carryovers during addition.Initialize the Result List: We create a new linked list called
ans
to store the result. Additionally, we keep a pointer calledstart
to the current node in theans
list.Iterate Through the Lists: We use a
while
loop that continues until bothtemp1
andtemp2
reach the end of their respective lists. In each iteration, we perform the following steps:
Extract the values
val1
andval2
from the current nodestemp1
andtemp2
, respectively. If either of the lists has reached its end, we consider the value as 0.Calculate the sum of
val1
,val2
, and thecarry
from the previous step.Update the current node in the result list (
start
) with the last digit of the sum (sum % 10
) and calculate the carry for the next iteration (carry = sum / 10
).Move
temp1
andtemp2
to their respective next nodes, if available.If there are more digits in either
l1
orl2
, or if there's a carry from the last addition, we create a new node in the result list and move thestart
pointer to this new node.
Handle Any Remaining Carry: After the loop, if there's still a carry (which could happen if the last addition results in a carry), we create one final node in the result list to accommodate the carry.
Return the Result: Finally, we return the
ans
linked list, which represents the sum of the two input numbers.
Code:
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int carry = 0;
ListNode* temp1 = l1;
ListNode* temp2 = l2;
ListNode* ans = new ListNode();
ListNode* start = ans;
while (temp1 || temp2) {
int val1 = (temp1) ? temp1->val : 0;
int val2 = (temp2) ? temp2->val : 0;
int sum = val1 + val2 + carry;
start->val = sum % 10;
carry = sum / 10;
if (temp1) temp1 = temp1->next;
if (temp2) temp2 = temp2->next;
if (temp1 || temp2 || carry > 0) {
start->next = new ListNode();
start = start->next;
}
}
if (carry > 0) {
start->val = carry;
}
return ans;
}
};
Time and Space Complexity
Let's analyze the time and space complexity of our solution:
Time Complexity: The algorithm makes a single pass through both input lists, so its time complexity is O(max(N, M)), where N and M are the lengths of
l1
andl2
, respectively.Space Complexity: We create a new linked list to store the result, which takes O(N) space where N is the greater value.
Top comments (0)