In this series of posts, I will discuss coding questions on the LinkedList
Data structure.
The posts in this series will be organized in the following way,
- Question Link β
- Possible Explanation π
- Documented C++ Code π§Ή
- Time and Space Complexity Analysis βπ
The Question
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.
https://leetcode.com/problems/add-two-numbers/#
π‘ Give yourself atleast 15-20 mins to figure out the solution :)
Explanation
Visualize how you used to do addition in your elementary school.
First create a dummynode whose next
pointer will hold our resulting linkedlist. Make a temp
pointer point to it. (it will be used for appending the resulting nodes)
π The resulting linkedlist is also in reversed order
Then iterate through both the list, untill we reach the end in both the lists and there's no carry left.
At every iteration, perform the arithmetic that we do while adding digits and calculate the resulting digit.
Create a newnode with value of resulting digit and append it to the end of our resulting linkedlist. (Notice the usecase of modulo operator).
C++ Code
Definition of LinkedList
//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) {}
};
Solution
#include <bits/stdc++.h>
#include "../linkedlist.h"
using namespace std;
/*
-Time:O(max(n1, n2))
-Space:O(max(n1,n2))
*/
class Solution
{
public:
//! Here we have to return the reversed list only
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
{
ListNode *start = new ListNode();
ListNode *temp = start;
//starting carry is zero
int carry = 0;
//go through both lists and create a new node untill
//nodes exist in any of the lists or carry is 1
while (l1 != nullptr || l2 != nullptr || carry != 0)
{
int sum = 0;
if (l1 != nullptr)
{
sum += l1->val;
l1 = l1->next;
}
if (l2 != nullptr)
{
sum += l2->val;
l2 = l2->next;
}
sum = sum + carry;
carry = sum / 10; //updating carry for next digit sum
//note: We take modulo with 10
temp->next = new ListNode(sum % 10);
temp = temp->next;
}
return start->next;
}
};
Complexity Analysis
n1 and n2 are sizes of given linkedlists.
Time Complexity: O(max(n1, n2))
Since we have to travel both the lists completely.
Space Complexity: O(max(n1, n2))
Same reason as above.
πConcretely both complexities will be O(max(n1, n2) + 1) by taking the end-carry into account but asymptotically, it doesn't matter.
Top comments (0)