Search for a command to run...
By iterating digit by digit, and calculating the sum and carry, it handles scenarios for the lengths of the input lists and any remaining carry values
Hi! My name is Nhut Nguyen. I am a software engineer and a writer in Copenhagen, Denmark.
Learn more about me at nhutnguyen.com
A simple example of using C++ switch
Two dynamic programming techniques to solve Leetcode 120. Triangle. One has space complexity O(n^2). The other is O(n).
An example of using a sliding window approach and an unordered map to track character positions
A simple C++ solution to Leetcode 1695. Maximum Erasure Value using a sliding window approach and prefix sums.
Strategies to avoid them will help you excel in your following technical interview
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.
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
Input: l1 = [0], l2 = [0]
Output: [0]
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
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.
Perform the school addition calculation and store the result in one of the lists.
Without loss of generality, let us store the result in l1. Then you might need to extend it when l2 is longer than l1 and when the result requires one additional node (Example 3).
#include <iostream>
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) {}
};
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode prehead; // dummy node to hook the head of the list
ListNode* node = l1; // store result on l1
prehead.next = node;
int sum = 0;
while (node) {
if (l1) {
sum += l1->val;
l1 = l1->next;
}
if (l2) {
sum += l2->val;
l2 = l2->next;
}
node->val = sum % 10;
sum /= 10;
if (!l1) { // l1 ends
if (l2) { // l1 is shorter than l2
node->next = l2;
} else if (sum == 1) { // both l1 and l2 end but the remember is not zero
ListNode* newNode = new ListNode(sum);
node->next = newNode;
}
}
node = node->next;
}
return prehead.next;
}
void printResult(ListNode* l) {
std::cout << "[";
while (l) {
std::cout << l->val << ",";
l = l->next;
}
std::cout << "]\n";
}
int main() {
{
ListNode three(3);
ListNode four1(4, &three);
ListNode two(2, &four1);
ListNode four2(4);
ListNode six(6, &four2);
ListNode five(5, &six);
printResult(addTwoNumbers(&two, &five));
}
{
ListNode zero1(0);
ListNode zero2(0);
printResult(addTwoNumbers(&zero1, &zero2));
}
{
ListNode nine0(9);
ListNode nine1(9, &nine0);
ListNode nine2(9, &nine1);
ListNode nine3(9, &nine2);
ListNode nine4(9, &nine3);
ListNode nine5(9, &nine4);
ListNode nine6(9, &nine5);
ListNode nine7(9);
ListNode nine8(9, &nine7);
ListNode nine9(9, &nine8);
ListNode nine10(9, &nine9);
printResult(addTwoNumbers(&nine6, &nine10));
}
}
Output:
[7,0,8,]
[0,]
[8,9,9,9,0,0,0,1,]
This solution efficiently adds two numbers represented as linked lists by iterating through both linked lists, digit by digit, and calculating the sum and carry. It also handles different scenarios for the lengths of the input lists and any remaining carry values.
Runtime: O(N), where N = max(l1.length, l2.length).
Extra space: O(1).
Thanks for reading! Get my book "10 Classic Coding Challenges" for FREE.