Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

Last Updated on November 9, 2022 by Sumit Kumar

A linked list is one of the most famous data structure asked in most coding interviews and have different variety of questions based on different concepts.

Given two positive numbers represented as singly-linked lists containing the digits of the numbers in reverse order. Write a function to return the sum of these two numbers as a linked list.

Let’s understand this problem to add two linked lists with help of examples.
Let us consider the 2 linked lists as l1 and l2 shown below to add two linked list:

If

Since it is given that the linked list contains digits of number in reverse order. So, the above two linked lists represent the numbers 15 and 397. So, the resultant linked list should represent the sum of the above two linked lists, i.e., 15+397 = 412. The resultant linked list will also contain the sum in form of a linked list in reverse order.

If

So in this case, the two linked lists represent the numbers 321 and 432. So, the resultant linked list should represent the sum of the above two linked lists, i.e., 321+432 = 753. The resultant linked list will also contain the sum in form of a linked list in reverse order.

I hope you have understood what we have to do in for adding two numbers represented by linked lists. Try to think of an approach to solve it.

Now, let us look at how to approach to add two numbers in linked list.

To add two numbers in the linked list, 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.

Here, we will need to implement the following functions for adding two numbers represented by linked list:
1) To reverse a linked list.
2) To convert linked list to integers.
3) To convert an integer to a linked list.

1. Reverse the given linked lists l1 and l2.
2. Convert the numbers represented by the two linked lists into integers num1 and num2.
3. Add the two numbers as sum = num1+num2.
4. Convert the above-calculated sum back to a linked list using our to_linkedlist() 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.
5. Return the resultant linked list ‘ans’ containing the sum.

Since our to_linkedlist() function is taking the digits from the end of the number passed to it and create a linked list by adding new nodes at the end, the resulting linked list will contain the digits of the number in reverse order.

So, our ‘ans’ will contain the sum as a linked list containing digits of sum in reverse order. This is what we required.

Now that you have understood how we are going to add two linked lists, before moving to the implementation try to implement it yourself for adding two numbers in linked list.

```#include
using namespace std;

struct Node {
int val;
Node* next;

Node(int value){
val = value;
next = NULL;
}
};

Node* new_node = new Node(new_val);
}

while(i){
cout<val<<" ";
i = i->next;
}
cout<<"\n";
}

// function to reverse a linked list
Node *prev = NULL;
while(curr!=NULL){
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}

// function to convert a linked list to integer
int num = 0;
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

while(x){
int d = x%10;
x /= 10;
curr->next = new Node(d);
curr = curr->next;
}
}

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

return ans;
}

int main(){
Node* l1 = NULL;

push_front(&l1, 1);
push_front(&l1, 5);

Node* l2 = NULL;

push_front(&l2, 3);
push_front(&l2, 9);
push_front(&l2, 7);

// l1-> 5 1
// l2-> 7 9 3

printList(sum);
// 2 1 4
}
```
```class LinkedList {

static class Node {

int data;
Node next;

Node(int d) {
data = d;
next = null;
}
}

void addTwoLists(Node first, Node second) {
Node start1 = new Node(0);
start1.next = first;
Node start2 = new Node(0);
start2.next = second;

Node result = new Node(0);
if (sumTwoNodes(start1.next, start2.next, result) == 1) {
Node node = new Node(1);
node.next = result.next;
result.next = node;
}
Node res=reverse_it(result.next);
printList(res);

}
{
Node prev=null;
while(curr!=null)
{
next=curr.next;
curr.next=prev;
prev=curr;
curr=next;
}
return prev;
}

/* Adds lists and returns the carry */
private int sumTwoNodes(Node first, Node second, Node result) {
if (first == null) {
return 0;
}
int number = first.data + second.data + sumTwoNodes(first.next, second.next, result);
Node node = new Node(number % 10);
node.next = result.next;
result.next = node;
return number / 10;
}

/* Appends preceding zeros in case a list is having lesser nodes than the other one*/
private void addPrecedingZeros(Node start1, Node start2) {
Node next1 = start1.next;
Node next2 = start2.next;
while (next1 != null && next2 != null) {
next1 = next1.next;
next2 = next2.next;
}
if (next1 == null && next2 != null) {
while (next2 != null) {
Node node = new Node(0);
node.next = start1.next;
start1.next = node;
next2 = next2.next;
}
} else if (next2 == null && next1 != null) {
while (next1 != null) {
Node node = new Node(0);
node.next = start2.next;
start2.next = node;
next1 = next1.next;
}
}
}

/* Utility function to print a linked list */
}
System.out.println("");
}

// Driver Code
public static void main(String[] args) {

// creating first list

// creating second list

System.out.print("Resultant List is ");
// add the two lists and see the result
}
}
```
```class Node:

def __init__(self, data):
self.data = data
self.next = None

def __init__(self):

def push(self, new_data):
new_node = Node(new_data)

prev = None
temp = None
carry = 0

while(first is not None or second is not None):

fdata = 0 if first is None else first.data
sdata = 0 if second is None else second.data
Sum = carry + fdata + sdata

carry = 1 if Sum >= 10 else 0

Sum = Sum if Sum < 10 else Sum % 10

temp = Node(Sum)

else:
prev.next = temp

prev = temp

if first is not None:
first = first.next
if second is not None:
second = second.next

if carry > 0:
temp.next = Node(carry)

def printList(self):
while(temp):
print (temp.data,end=' ')
temp = temp.next

first.push(1)
first.push(5)

second.push(3)
second.push(9)
second.push(7)

res.printList()

```

### Output

2 1 4

Time Complexity: O(n+m), where n,m are the number of nodes in the linked lists
Space Complexity: O(max(n,m)), as the number of digits in sum will depend on the number having more digits.

This approach would work only for numbers that are small enough to fit into integer datatype. What if the number of digits in a number is huge eg., 30? Then the above approach would fail and we need to improve upon it to add two numbers in linked list .

### Approach 2 (Simple iteration with 2 pointers)

To add two numbers in a linked list, 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.

1. Use 2 pointers to store the head of each linked list and initialize carry as 0.
2. Declare a pointer to the node to store our answer.
3. Iterate through both the linked list and add the digits pointed by the pointers (if we have reached the end of one of the linked lists and have no further nodes, consider its value as 0 while taking the sum).
4. Add a new node with ((sum+carry)%10) as value to our answer and update carry as (sum + carry)/10.
5. Repeat steps 3 and 4 till we reach the end of both the linked lists.
6. After traversing both the linked lists, if carry > 0 then add this carry to our answer as a new node.

## Code Implementation:

```#include<bits/stdc++.h>
using namespace std;

struct Node {
int val;
Node* next;

Node(int value){
val = value;
next = NULL;
}
};

Node* new_node = new Node(new_val);
}

while(i){
cout<<i->val<<" ";
i = i->next;
}
cout<<"\n";
}

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, 1);
push_front(&l1, 5);

Node* l2 = NULL;

push_front(&l2, 3);
push_front(&l2, 9);
push_front(&l2, 7);

// l1-> 5 1   =  15
// l2-> 7 9 3 = 397

printList(sum);
// 2 1 4      = 412
}
```
```class Node
{
int val;
Node next;
Node(int value)
{
val = value;
next = null;
}
}
{
static void push_front(Node head, int new_val)
{
Node new_node = new Node(new_val);
}
{
while(i!=null)
{
System.out.print(i.val+" ");
i = i.next;
}
System.out.println();
}
// function to reverse a linked list
{
Node prev = null;
while(curr!=null)
{
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
// function to convert a linked list to integer
int num = 0;
while(curr!=null)
{
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
{
while(x>0)
{
int d = x%10;
x /= 10;
curr.next = new Node(d);
curr = curr.next;
}
}
static 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

return ans;
}
public static void main(String [] args)
{
Node l1 = null;

push_front(l1, 1);
push_front(l1, 5);

Node l2 = null;

push_front(l2, 3);
push_front(l2, 9);
push_front(l2, 7);

// l1-> 5 1
// l2-> 7 9 3

printList(sum);
// 2 1 4
}
}
```

Output

2 1 4

Note that here I have initialized ‘ans’ with a node with value 0 initially. This I did to avoid handling the case of insertion in an empty linked list separately. So, at the end ignored the additional node added and return the list after it.

Space Complexity: O(max(n,m)), as the number of digits in sum will depend on the number having more digits.

To avoid the use of extra space we can store the sum in one of the linked lists itself. Try implementing it yourself.

Conclusion:

In this article, we have seen how to add two numbers represented as linked lists by using two different approaches. We can use any of the approaches to add two numbers in the linked list depending upon the constraints provided.

## FAQs

1. In how many different ways we can add two numbers in the linked list?
We can add the two numbers in the linked list by simple iteration with 2 pointers technique, stacks, backtracking, etc.

2. How is carry computed for the sum of digits?
Basically, if the sum of digits is less than 10, then carry is 0 else carry is 1.

3. What is a Linked list?
The linked list is a set of nodes in which each node has a pointer to the next node and is stored at non-contiguous memory locations.