## Problem Statement

In this problem add two numbers represented by linked lists, You will be given two numbers represented by two separate Linked List, and write a function that returns the sum list.

A sum list is a list that represents the sum of two input numbers (Linked List).

**Rules :**

- In both, the numbers list the digits are stored in a
**reverse order**. - Each of the nodes of the Linked List must contain a
**single digit**. - The two numbers (Linked List) do not contain any
**leading zero**, except the number`0`

itself.

**Input Format :**

- Two numbers are represented by two Linked List heads.

**Output Format :**

- Return the sum of the two input numbers which is represented by Linked List in reverse order.

## Example

Let’s understand this problem add two numbers represented by linked lists with help of examples.

### Example : 1

**Input :**

```
l1 = {2, 4, 3}
l2 = {5, 6, 4}
```

**Output :**

`{7, 0, 8}`

**Explanation :**

**Let us now understand the above example in detail.**

- In the above example, we are taking two Linked List as input, and we are considering them as numbers.
- Since it is given that the Linked List contains digits of the number in
**reverse order**. The list**l1**which consists of`{2, 4, 3}`

nodes will be represented as the number`342`

, and the list**l2**which consists of`{5, 6, 4}`

nodes will be represented as the number`465`

. - So, we need to return a resultant
**Linked List**in the reverse order that should represent the`sum`

of the above two Linked Lists, i.e., $342 + 465 = 807$. - So, in the above example we will return the Linked List form of the number
`807`

in reverse order, that is,`{7, 0, 8}`

.

### Example : 2

**Input :**

```
l1 = {5, 1}
l2 = {7, 9, 3}
```

**Output :**

`{2, 1, 4}`

**Explanation :**

**Let us now understand the above example in detail.**

- In the above example, we are taking two Linked List as input, and we are considering them as numbers.
- Since it is given that the Linked List contains digits of the number in
**reverse order**. The list**l1**which consists of`{5, 1}`

nodes will be represented as the number`15`

, and the list**l2**which consists of`{7, 9, 3}`

nodes will be represented as the number`397`

- So, we need to return a resultant
**Linked List**in the reverse order that should represent the`sum`

of the above two Linked Lists, i.e., $15 + 397 = 412$. - So, in the above example we will return the Linked List form of the number
`412`

in reverse order, that is,`{2, 1, 4}`

.

**Input :**

**Output :**

## Constraints

- 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.

## Approach : 1

Let us begin with the **brute force** approach of adding two numbers represented by linked lists. We are going to use some extra space, and it is slow but should be mentioned during the interview.

**Intuition :**

In the **brute force** approach add two numbers represented by linked lists. To add two numbers, the simplest thing we can do is to reverse the two linked lists (as they contain the digits in reverse order). Then convert the two numbers in linked lists into integers. Add these integers and convert the sum back to a linked list such that it contains digits in reverse order.

**In this approach, we will need to implement the following functions :**

- To reverse both the Linked List.
- Covert both the Linked List into
**integer**. - Find the sum of both integers.
- Reverse the resultant integer and then convert it into a Linked List.

**Algorithm :**

Here is the brute force algorithm for this particular problem **add two numbers represented by linked lists :**

- Firstly, reverse both the given Linked List
`l1`

and`l2`

. - Then, convert the numbers represented by both the linked list into integers
`n1`

and`n2`

. - Then, add both the numbers as $sum = n1 + n2$.
- Then, convert the above-calculated sum back to a Linked List using the
`toLinkedList()`

function which will one by one take the digits from the end of the number passed and create a linked list using them. And finally, return it. Note, in the`toLinkedList()`

function the number’s digit will be added in reverse order.**ans**=`to_linkedlist(sum)`

. - Return the resultant linked list
**‘ans’**containing the sum. **Note :**This approach will not work for huge input numbers represented by Linked List, which is out of the range of**integer**, and it will throw an**overflow**error.

### Code

Now, let us see the code of adding two numbers represented by linked lists problem in different programming languages.

**Code in JAVA :**

*// Java program to add two numbers*
*// represented by linked list*
import java.util.*;
*// Node Class*
class Node{
int data;
Node next;
Node(int data, Node next){
this.data = data;
this.next = next;
}
}
*// Public class*
public class MyClass{
*// convertList method to*
*// convert Integer to List*
public static Node convertList(int num){
Node l = null;
while(num != 0){
l = new Node(num%10, l);
num = num/10;
}
return l;
}
*// toInteger method to*
*// convert List to Integer*
public static int toInteger(Node l){
Node curr = l;
int ans = 0;
while(curr != null){
ans = ans*10 + curr.data;
curr = curr.next;
}
return ans;
}
*// reverse method to reverse*
*// the Linked List*
public static Node reverse(Node head){
Node prev = head;
Node curr = head.next;
while(curr != null){
Node next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
head.next = null;
head = prev;
return head;
}
*// addList to add the content*
*// of the Linked List*
public static Node addList(Node l1, Node l2){
l1 = reverse(l1);
l2 = reverse(l2);
int num1 = toInteger(l1);
int num2 = toInteger(l2);
int sum = num1 + num2;
Node l3 = convertList(sum);
l3 = reverse(l3);
return l3;
}
*// printList to print the content*
*// of the Linked List*
public static void printList(Node ans){
Node curr = ans;
while(curr != null){
System.out.print(curr.data+" ");
curr = curr.next;
}
}
*// main method*
public static void main(String[] args){
int x = 243;
int y = 564;
Node l1 = convertList(x);
Node l2 = convertList(y);
Node ans = addList(l1, l2);
printList(ans);
}
}

**Output :**

```
7 0 8
```

**Code in C++ :**

```
#include<bits/stdc++.h>
using namespace std;
struct Node {
int val;
Node* next;
Node(int value){
val = value;
next = NULL;
}
};
void push_front(Node** head, int new_val){
Node* new_node = new Node(new_val);
new_node->next = *head;
*head = new_node;
}
void printList(Node* head){
Node* i = head;
while(i){
cout<<i->val<<" ";
i = i->next;
}
cout<<"\n";
}
```*// function to reverse a linked list*
Node* reverse_it(Node* head){
Node *prev = NULL;
Node *curr = head, *next;
while(curr!=NULL){
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
*// function to convert a linked list to an integer*
int to_integer(Node* head){
int num = 0;
Node* curr = head;
while(curr){
int digit = curr->val;
num = num*10 + digit;
curr = curr->next;
}
return num;
}
*// function to convert a number to a linked list*
*// containing digits in reverse order*
Node* to_linkedlist(int x){
Node* head = new Node(0);
if(x==0) return head;
Node* curr = head;
while(x){
int d = x%10;
x /= 10;
curr->next = new Node(d);
curr = curr->next;
}
return head->next;
}
*// function to add 2 numbers given as linked lists*
Node* add_list(Node* l1, Node* l2){
*// reversing the 2 linked lists*
l1 = reverse_it(l1);
l2 = reverse_it(l2);
*// converting them into integers*
int num1 = to_integer(l1);
int num2 = to_integer(l2);
int sum = num1 + num2;
*// converting the sum back to*
*// a linked list*
Node* ans = to_linkedlist(sum);
return ans;
}
int main(){
Node* l1 = NULL;
push_front(&l1, 2);
push_front(&l1, 4);
push_front(&l1, 3);
Node* l2 = NULL;
push_front(&l2, 5);
push_front(&l2, 6);
push_front(&l2, 4);
*// l1-> 2 4 3*
*// l2-> 5 6 4*
Node* sum = add_list(l1,l2);
printList(sum);
*// 7 0 8*
}

**Output :**

```
7 0 8
```

**Code in Python :**

*# Node for linked list:*
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Solution:
def __init__(self):
self.head = None
*#Function to add two numbers represented by linked list.*
def addTwoLists(self, l1, l2):
q1 = []
q2 = []
while l1:
q1.append(l1.data)
l1 = l1.next
while l2:
q2.append(l2.data)
l2 = l2.next
q1 = [str(i) for i in q1]
s1 = int("".join(q1[::-1]))
q2 = [str(i) for i in q2]
s2 = int("".join(q2[::-1]))
s = s1+s2
s = [i for i in str(s)]
s = s[::-1]
head = l = Node(0)
for i in s:
l.next = Node(i)
l = l.next
return head.next
*# Node Class*
class Node:
def __init__(self, data):
self.data = data
self.next = None
*# Linked List Class*
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
*# creates a new node with given value and appends it at the end of the linked list*
def insert(self, val):
if self.head is None:
self.head = Node(val)
self.tail = self.head
else:
self.tail.next = Node(val)
self.tail = self.tail.next
*# prints the elements of linked list starting with head*
def printList(n):
while n:
print(n.data,end=' ')
n = n.next
print()
if __name__ == '__main__':
arr1 = [2,4,3]
arr2 = [5,6,4]
LL1 = LinkedList()
for i in arr1:
LL1.insert(i)
LL2 = LinkedList()
for i in arr2:
LL2.insert(i)
obj = Solution()
res = obj.addTwoLists(LL1.head, LL2.head)
printList(res)

**Output :**

`7 0 8`

### Time Complexity

In this approach of adding two numbers represented by linked lists, Firstly, we are reversing both the list **l1** and **l2**, then we are converting them into integers. So overall the time complexity for this code will be $O(n+m)$.

**T.C :** $O(n+m)$, where $n, m$ are the number of nodes in the linked lists.

### Space Complexity

The space complexity for the above implementation will depend upon the number of digits in our final result (after calculating the sum). This is very obvious because, as we are expected to store our final result in a Linked List, for every digit there will be a linked list node. So, for $N$ digits, the total space taken by the linked list will be $O(N)$, assuming, $N$ is the number of digits in our final result sum. Since, we know the final sum will mainly depend upon the maximum number of digits, from each of the numbers provided to us. Hence, we can conclude that our space complexity will depend on $O(max(n,m))$, where $m$ and $n$ are the number of digits in `num1`

and `num2`

respectively.

## Approach : 2

The above approach of adding two numbers represented by the problem of the linked list is a brute force approach, and it will work only for input numbers that are small enough to belong in the range of integer data. What if the number of digits in the input number is huge let’s say `30`

? For this type of input, the above approach will not work and we need to improve upon it.

Let us now see a much better and optimal approach of adding two numbers represented by the problem of the linked list, which will even work perfectly for the input number’s digit out of range of integer datatype.

**Intuition :**

Here in this approach of adding two numbers represented by the problem of the linked list, we are not going to convert the Linked List into an integer and then calculate the sum, but we will do it in place with the help of the **two-pointer** method. We can simply iterate both the linked lists and keep on calculating the sum of values in nodes. Along with that, we will also maintain a carry in which we will store the first digit of the sum that comes out to be two-digit in any node. While taking the sums we will add the previous carry to it and add a new node to the result containing the last digit in the sum and update the carry for the next iteration.

We can simply iterate the `2`

linked lists and take the sum of the values in nodes along with maintaining a carry. While taking sums add the previous carry to it and add a new node to the result containing the last digit in the sum and update the carry for the next iteration.

**Algorithm :**

- We are going to use the two-pointer method to solve this problem.
- Firstly, we will use
`2`

pointers to store the head of each linked list and initialize a carry variable as`0`

. Note, in the case of Java there is no concept of pointers, so in Java, we are going to use`2`

iterators. - Then, we declare a pointer (iterator in case of Java) to the node to store our resultant answer represented by Linked List.
- We will iterate through both the linked list and keep on adding the digits pointed by the pointers. The moment we have reached the end of any one of the linked lists and we have no further nodes of that linked list, we will consider its value as
`0`

while iterating for the other linked list which is still having the nodes, and keep calculating the sum. - We will add a new node with $(sum + carry)\%10$ as value to our answer and update carry as $(sum + carry) / 10$.
- We will keep on repeating steps
`3`

and`4`

until we reach the end of both of the linked lists. If one of the Linked List is smaller in size than the other one, it gets ended before the other Linked List. In that case, we will continue the iteration, just in the place of the smaller Linked List’s value, we will add`0`

until the other Linked List also gets over. - After traversing both the linked lists, if the carry is greater than
`0`

$(carry > 0)$ then add this carry to our answer as a new node.

### Code

Now, let us see the code of adding two numbers represented by linked lists problem in different programming languages.

**Code in JAVA :**

*// Java program to add two numbers*
*// represented by linked list*
import java.util.*;
*// Node Class*
class Node{
int data;
Node next;
Node(int data){
this.data = data;
}
Node(int data, Node next){
this.data = data;
this.next = next;
}
}
*// Public class*
public class AddTwoList{
*// addList to add the content*
*// of the Linked List using*
*// two pointer method*
public static Node addList(Node l1, Node l2){
Node p1 = l1;
Node p2 = l2;
Node ans = new Node(0);
Node curr = ans;
int carry = 0;
while(p1 != null || p2 != null){
int sum = ((p1 != null)? p1.data : 0) + ((p2 != null)? p2.data : 0) + carry;
carry = sum/10;
int mod = sum%10;
curr.next = new Node(mod);
curr = curr.next;
p1 = p1.next;
p2 = p2.next;
}
if(carry > 0){
curr.next = new Node(carry);
}
return ans.next;
}
*// printList to print the content*
*// of the Linked List*
public static void printList(Node ans){
Node curr = ans;
while(curr != null){
System.out.print(curr.data+" ");
curr = curr.next;
}
}
*// main method*
public static void main(String[] args){
int x = 243;
int y = 564;
Node l1 = null;
while(x != 0){
l1 = new Node(x%10, l1);
x = x/10;
}
Node l2 = null;
while(y != 0){
l2 = new Node(y%10, l2);
y = y/10;
}
Node ans = addList(l1, l2);
printList(ans);
}
}

**Output :**

```
7 0 8
```

**Code in C++ :**

```
#include <bits/stdc++.h>
using namespace std;
struct Node {
int val;
Node* next;
Node(int value){
val = value;
next = NULL;
}
};
void push_front(Node** head, int new_val){
Node* new_node = new Node(new_val);
new_node->next = *head;
*head = new_node;
}
void printList(Node* head){
Node* i = head;
while(i){
cout<<i->val<<" ";
i = i->next;
}
cout<<"\n";
}
```*// function to add 2 numbers given as linked lists*
Node* add(Node* l1, Node* l2){
Node* ans = new Node(0);
Node* curr = ans;
int carry = 0;
while(l1 || l2){
int sum = 0;
if(l1) sum += l1->val;
if(l2) sum += l2->val;
sum += carry;
curr->next = new Node(sum%10);
curr = curr->next;
carry = sum/10;
if(l1) l1 = l1->next;
if(l2) l2 = l2->next;
}
if(carry){
curr->next = new Node(carry);
}
ans = ans->next;
return ans;
}
int main(){
Node* l1 = NULL;
push_front(&l1, 2);
push_front(&l1, 4);
push_front(&l1, 3);
Node* l2 = NULL;
push_front(&l2, 5);
push_front(&l2, 6);
push_front(&l2, 4);
*// l1-> 2 4 3*
*// l2-> 5 6 4*
Node* sum = add(l1,l2);
printList(sum);
*// 7 0 8 = 412*
}

**Output :**

```
7 0 8
```

**Code in python :**

*# A Linked List Node*
class Node:
def __init__(self, data=None, next=None):
self.data = data
self.next = next
*# Function to print a given linked list*
def printList(head):
ptr = head
while ptr:
print(ptr.data, end=' ')
ptr = ptr.next
*# print('None')*
*# Iterate through the list and move/insert each node*
*# in front of the out list like `push()` of the node*
def reverse(head):
out = None
current = head
*# traverse the list*
while current:
*# tricky: note the next node*
next = current.next
*# move the current node onto the out*
current.next = out
out = current
*# process next node*
current = next
*# fix head*
return out
*# Function to add two lists, `X` and `Y`*
def append(X, Y):
head = None
*# stores the last seen node*
prev = None
*# initialize carry with 0*
carry = 0
*# run till both lists are empty*
while X or Y:
*# sum is X's data + Y's data + carry (if any)*
total = 0
if X:
total += X.data
if Y:
total += Y.data
total += carry
*# if the sum of a 2–digit number, reduce it and update carry*
carry = total // 10
total = total % 10
*# create a new node with the calculated sum*
node = Node(total)
*# if the output list is empty*
if head is None:
*# update `prev` and `head` to point to the new node*
prev = node
head = node
else:
*# add the new node to the output list*
prev.next = node
*# update the previous node to point to the new node*
prev = node
*# advance `X` and `Y` for the next iteration of the loop*
X = X.next if X else X
Y = Y.next if Y else Y
if carry:
prev.next = Node(carry, prev.next)
return head
*# Function to add two lists, `X` and `Y`*
def addLists(X, Y):
*# reverse `X` and `Y` to access elements from the end*
return append(X, Y)
if __name__ == '__main__':
x = 243
y = 564
*# construct list `X` (2 —> 4 —> 3) from number `x`*
X = None
while x:
X = Node(x % 10, X)
x = x // 10
*# construct list `Y` (5 —> 6 —> 4) from number `y`*
Y = None
while y:
Y = Node(y % 10, Y)
y = y // 10
printList(addLists(X, Y))

**Output :**

```
7 0 8
```

### Time Complexity

In this approach add two numbers represented by the problem of the linked list, as we are traversing both the list **l1** and **l2**, and we are calculating the sum of the numbers. So the overall time complexity for this code will be $O(n+m)$.

**T.C :** $O(n+m)$, where $n, m$ are the number of nodes in the linked lists.

### Space Complexity

The overall space complexity of this approach will depend on the number of digits in the sum, which will depend on the number having more digits.

$O(max(n,m))$, as the number of digits in the sum will depend on the number having more digits.**Note :** To avoid the use of extra space we can store the sum in one of the linked lists itself or modify one of the Linked List itself.

## Approach : 3

Now let us see another approach of how we can solve this add two numbers represented by linked lists problem with the help of a data structure **stack**, and how we can add the numbers of both the Linked List using a **stack**. This approach is not that efficient, as here we have to make sure that the size of the list should not exceed the limit of the **stack**, or it will throw an error of **overflow**.

**Intuition :**

In this approach we are going to use three **stacks**, out of which in two stacks **s1**, **s2** we are going to store the nodes of both the Linked List and in the third stack **s3** we will store the sum of the numbers of both the list inside the stacks **s1**, **s2**.

**Algorithm :**

- Firstly, we are going to create
`3`

stacks named`s1`

,`s2`

, and`s3`

. - Then, we will fill the stack
`s1`

with Nodes of Linked List`l1`

and the stack`s2`

with Nodes of Linked List`l2`

. - We will initialize a carry variable in which we will store the first digit of the sum that comes out to be two-digit in any node. If the sum is greater than
`9`

we will set the carry as`1`

else we will set the carry as`0`

. - Now, we will start filling the stack
`s3`

by creating new nodes and storing the data of that new node to the sum of**s1.top()**, and**s2.top()**and carry until both the list`l1`

and`l2`

are empty. We will create a Node (say prev) that will contain the head of the sum List inside the stack`s3`

. - Now, connect all the elements of
`s3`

from top to bottom and then reverse the list as return prev.

### Code

Now, let us see the code of adding two numbers represented by linked lists problem in different programming languages.

**Code in JAVA :**

*// Java program to add two numbers*
*// represented by linked list*
import java.util.*;
*// Node Class*
class Node{
int data;
Node next;
Node(int data){
this.data = data;
}
Node(int data, Node next){
this.data = data;
this.next = next;
}
}
public class AddTwoList{
*// reverse method to reverse*
*// the Linked List*
public static Node reverse(Node head){
Node prev = head;
Node curr = head.next;
while(curr != null){
Node next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
head.next = null;
head = prev;
return head;
}
*// addList to add the content*
*// of the Linked List using*
*// stack method*
public static Node addList(Node l1, Node l2){
Stack<Node> s1 = new Stack<>();
Stack<Node> s2 = new Stack<>();
Stack<Node> s3 = new Stack<>();
Node p1 = l1;
Node p2 = l2;
*// adding the nodes of the list*
*// l1 inside stack s1*
while(p1 != null){
s1.push(p1);
p1 = p1.next;
}
*// adding the nodes of the list*
*// l2 inside stack s2*
while(p2 != null){
s2.push(p2);
p2 = p2.next;
}
int carry = 0;
while(!s1.isEmpty() || !s2.isEmpty()){
int sum = ((!s1.isEmpty())? s1.pop().data : 0) + ((!s2.isEmpty())? s2.pop().data : 0) + carry;
carry = sum/10;
int mod = sum%10;
Node node = new Node(mod);
s3.push(node);
}
if(carry > 0){
s3.push(new Node(carry));
}
Node ans = new Node(0);
Node curr = ans;
while(!s3.isEmpty()){
curr.next = s3.pop();
curr = curr.next;
}
ans = reverse(ans.next);
return ans;
}
*// printList to print the content*
*// of the Linked List*
public static void printList(Node ans){
Node curr = ans;
while(curr != null){
System.out.print(curr.data+" ");
curr = curr.next;
}
}
*// main method*
public static void main(String[] args){
int x = 243;
int y = 564;
Node l1 = null;
while(x != 0){
l1 = new Node(x%10, l1);
x = x/10;
}
Node l2 = null;
while(y != 0){
l2 = new Node(y%10, l2);
y = y/10;
}
Node ans = addList(l1, l2);
printList(ans);
}
}

**Output :**

```
7 0 8
```

**Code in C++**

```
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct Node {
int val;
Node* next;
Node(int value){
val = value;
next = NULL;
}
};
void push_front(Node** head, int new_val){
Node* new_node = new Node(new_val);
new_node->next = *head;
*head = new_node;
}
void printList(Node* head){
Node* i = head;
while(i){
cout<<i->val<<" ";
i = i->next;
}
cout<<"\n";
}
```*// function to add 2 numbers given as linked lists*
Node* add(Node* l1, Node* l2){
stack<int>s1;
stack<int>s2;
int size1=0;
int size2=0;
while(l1!=NULL)
{
s1.push(l1->val);
l1=l1->next;
size1++;
}
while(l2!=NULL)
{
s2.push(l2->val);
l2=l2->next;
size2++;
}
unsigned long long num1=0;
unsigned long long num2=0;
while(!s1.empty() && size1!=0)
{
num1=num1+(s1.top()*pow(10,size1-1));
s1.pop();
size1--;
}
while(!s2.empty() &&size2!=0)
{
num2=num2+(s2.top()*pow(10,size2-1));
s2.pop();
size2--;
}
unsigned long long result=num1+num2;
vector<int>ans;
if(result==0)
ans.push_back(0);
while(result>0)
{
unsigned long long k=result%10;
ans.push_back(k);
result=result/10;
}
Node* head=new Node(ans[0]);
Node* curr;
curr=head;
for(int i=1;i<ans.size();i++)
{
Node* curr1=new Node(ans[i]);
curr->next=curr1;
curr=curr->next;
}
return head;
}
int main(){
Node* l1 = NULL;
push_front(&l1, 2);
push_front(&l1, 4);
push_front(&l1, 3);
Node* l2 = NULL;
push_front(&l2, 5);
push_front(&l2, 6);
push_front(&l2, 4);
*// l1-> 2 4 3*
*// l2-> 5 6 4*
Node* sum = add(l1,l2);
printList(sum);
*// 7 0 8 = 412*
}

**Output :**

```
7 0 8
```

**Code in python :**

*# Node for linked list:*
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Solution:
def __init__(self):
self.head = None
*#Function to add two numbers represented by linked list.*
def addTwoLists(self, l1, l2):
stack = []
prev = None
temp = None
carry = 0
while l1 is None or l2 is None:
dFirst = 0 if l1 is None else l1.data
dSecond = 0 if l2 is None else l2.data
Sum = carry + dFirst + dSecond
carry = 1 if Sum>=10 else 0
Sum = Sum if Sum<10 else Sum % 10
stack.append(Sum)
*# update the l1*
if l1 is not None:
l1 = l1.next
*# update the l2*
if l2 is not None:
l2 = l2.next
if carry > 0:
stack.append(carry)
for i in range(len(stack)-1, -1, -1):
new_node = Node(stack[i])
if self.head is None:
self.head = new_node
else:
new_node.next = self.head
self.head = new_node
return self.head
*# Node Class*
class Node:
def __init__(self, data):
self.data = data
self.next = None
*# Linked List Class*
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
*# creates a new node with given value and appends it at the end of the linked list*
def insert(self, val):
if self.head is None:
self.head = Node(val)
self.tail = self.head
else:
self.tail.next = Node(val)
self.tail = self.tail.next
*# prints the elements of linked list starting with head*
def printList(n):
while n:
print(n.data,end=' ')
n = n.next
print()
if __name__ == '__main__':
arr1 = [2,4,3]
arr2 = [5,6,4]
LL1 = LinkedList()
for i in arr1:
LL1.insert(i)
LL2 = LinkedList()
for i in arr2:
LL2.insert(i)
obj = Solution()
res = obj.addTwoLists(LL1.head, LL2.head)
printList(res)

**Output :**

`7 0 8`

### Time Complexity

In this approach of adding two numbers represented by the problem of the linked list, as we are traversing both the list **l1** and **l2**, we are storing them in stacks. So the overall time complexity for this code will be $O(n+m)$.

**Time Complexity :** $O(n+m)$, where $n, m$ are the number of nodes in the linked lists.

### Space Complexity

In the above implementation, we are storing the nodes of both the Linked List inside two different stacks, so it will occupy $O(n) + O(m)$ space, where `n`

and `m`

are the size of both the Linked list. Now, we are storing their sum inside another stack which will again occupy a space of $O(max(n, m))$ as discussed above, the space of the sum will depend upon the input number of more digits. So the overall space will be $O(n + m + max(n,m))$.

$O(n) + O(m) + O(max(n,m))$. However, this approach is not much efficient as we are using a lot of space here.

## Conclusion

In this article, we learned about the problem, then added two numbers represented by linked lists.

**Let us recap the points we discussed throughout the article :**

- Basically, in this problem
**add two numbers represented by Linked List**, you will be given two numbers represented by two Linked List, we have to write a function that returns the sum of both lists number-wise. - At first, we applied the
**brute force**approach for this problem add two numbers represented by linked lists. In which we reverse the two linked lists (as they contain the digits in reverse order). Then convert the two numbers in linked lists into integers. Add these integers and convert the sum back to a linked list such that it contains digits in reverse order. - Then, we applied the
**optimal**approach for this problem add two numbers represented by linked lists. In which we will use the**Two Pointer**technique. - In this
**Two Pointer**approach, We can simply iterate both the linked lists and keep on calculating the sum of values in nodes. Along with that, we will also maintain a carry in which we will store the first digit of the sum that comes out to be two-digit in any node. While taking the sums we will add the previous carry to it and add a new node to the result containing the last digit in the sum and update the carry for the next iteration. - Using the
**Two Pointer**approach, the code will even work perfectly for the input number’s digit out of range of integer datatype. - Then, we solved this problem using another approach for this problem adding two numbers represented by linked lists, that is, by using
**stack**data structure. - In this approach we will use three
**stacks**, out of which in two stacks**s1**,**s2**we are going to store the nodes of both the Linked List and in the third stack**s3**we will store the sum of the numbers of both the list inside the stacks**s1**,**s2**.

## Frequently Asked Questions

Q. **How Should We Approach a Problem Like this ?**

A. Firstly, you need to understand the problem properly. Then think of an algorithm for this problem. Then begin with the Brute Force approach. Later, try to optimize your code.