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.