1.
Introduction
2.
Problem Statement
3.
Brute Force Approach
4.
Algorithm
4.1.
DRY Run
4.2.
Implementation in C++
4.3.
Implementation in Python
4.4.
Complexity Analysis
5.
5.1.
How can you reverse a linked list?
5.2.
How can we represent a number in the linked list?
5.3.
How can we find the shorter linked list between two linked lists?
5.4.
Why did we reverse the linked lists in this method before finding the sum of the numbers represented by them?
5.5.
What is a carry variable in the above method?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

## Introduction

A linked list is a collection of nodes connected to each other. A node in a linked list contains the data and address of the next node. A linked list is a linear data structure that stores the data in non-sequential order and dynamically allocates the memory addresses to the new data. To access a particular node, you need to iterate through all the previous nodes of the target node using the addresses.

Problems based on the linked list are asked often. Many big companies ask one of the questions based on the linked list during the coding interviews. This blog will discuss one of the most famous questions based on a linked list. The name of the problem is adding two numbers represented by linked lists.

Recommended Topic, Floyds Algorithm

## Problem Statement

Suppose there are two linked lists such that all the nodes of these linked lists contain numbers between 1 and 9. Now we are asked to find the sum of the numbers formed by these linked lists treating nodes as the digits of a number.

For Example

Input

Numbers of Nodes in linked list 1 and 2: 5 5

Nodes in linked list 1: 3 -> 8 -> 1 -> 3 -> 5

Nodes in linked list 2: 6 -> 2 -> 4 -> 3 -> 5

Output

1 -> 0 -> 0 -> 5 -> 7->0

There are numerous approaches to adding two numbers represented by the linked lists. Let's discuss the approaches one by one.

You can check out Data Structures problems.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## Brute Force Approach

In this approach, we start from the least significant digit of the numbers formed by the linked list and traverse through both lists side by side to find the sum of pairs of nodes belonging to the same place value of the numbers.

If there is a carry in addition, we will store it in a variable. Then we will add the carry in the next addition.

We keep pushing the sum for each pair into a separate list, the resultant linked list representing the sum of the numbers.

Once we have completed the traversal of the linked lists, we check the carry. If the carry is 1, we create another node and append it to the resultant linked list. Then we print the resulting linked list, representing the sum of the numbers represented by linked indexes.

## Algorithm

2. Traverse through both linked lists with one node at a time, start with the least significant digits of the number.

3. Add each pair of nodes corresponding to the same place value in the number formed by the linked list, along with the carry from the previous pair. And push the sum as a node into the resultant linked list.

6. Add an extra node into the linked list if carry after the last node is 1.

7. Print the resultant linked list.

### Implementation in C++

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

// Structure for a node in the linked list.
struct node
{
int data;
struct node * next;
};

// For creating a new node for a number.
node* createnode(int value)
{
node *newnode = new node();
newnode->data = value;
newnode->next = nullptr;
return newnode;
}

{
node *sumlist = nullptr;
node *curr, *last = nullptr;
int carry = 0, sum;

/*
Using a loop to add the numbers
in the nodes of both the
*/

/*
Each node in the resultant linked list is sum of the
current nodes of the linked lists and the carry from
the addition of the last nodes.
*/

/*
Setting the carry variable to 1, if value of the sum is
greater than 10.

If the sum is greater than 10, we divide it by 10 and
the remainder is the value of the new node in the resultant
*/
{

if (sum >= 10)
{
sum = sum % 10;
carry = 1;
}
else
{
carry = 0;
}

curr = createnode(sum);

if (sumlist == nullptr)
{
sumlist = curr;
}
else
{
last->next = curr;
}

last = curr;

{
}

{
}
}

/*
*/
{
if (sum >= 10)
{
sum = sum % 10;
carry = 1;
}
else
{
carry = 0;
}

curr = createnode(sum);
last->next = curr;
last = curr;
}

/*
*/
{
if (sum >= 10)
{
sum = sum % 10;
carry = 1;
}
else
{
carry = 0;
}

curr = createnode(sum);
last->next = curr;
last = curr;
}

/*
If we are left only with a carry in the last, we create a
new node with it and append it to the resultant list.
*/

if (carry > 0)
{
curr->next = createnode(carry);
}

return sumlist;
}

// Function to reverse the linked lists.
{
// If the list is empty or contains a single node.
{
}

// Reversing the list.

}

// Function to push nodes into the list.
void push(struct node **headr, int newval)
{
// Creating a new node.
struct node *newnode = createnode(newval);

// Linking the node to the list.

// Shifting the head pointer to a new node.
}

// Driver function.
int main()
{
int size1, size2;
cout << "Enter the number of nodes in list 1 and list 2:  ";
cin >> size1 >> size2;

// Pushing the nodes in the first linked list.
cout << "Enter the nodes in the list 1: ";
for (int i = 0; i < size1; i++)
{
int a;
cin >> a;
}

// Pushing the nodes in the second linked list.
cout << "Enter the nodes in the list 2: ";
for (int i = 0; i < size2; i++)
{
int a;
cin >> a;
}

cout << endl;

// Reversing the resultant linked list.
sumlist = reverse(sumlist);

// Printing the final linked list.
while (sumlist != nullptr)
{
cout << sumlist->data << " ";
sumlist = sumlist->next;
}
return 0;
}

Output

### Implementation in Python

# Creating the node
class Node:
def __init__(self,data):
self.data = data

# Creating the linked lists of nodes
def __init__(self):

def insert(self, data):

newNode = Node(data)

else:

def __init__(self):

# Function to add the numbers
result = None
carry = 0
while(list1!=None and list2!=None):
sum = carry + list1.data + list2.data
if(sum>=10):
carry = 1
else:
carry = 0

new_node = Node(sum%10)
result = new_node
else:
result = new_node

while(list1!=None):
sum = carry + list1.data
if(sum>=10):
sum = sum%10
carry = 1
else:
carry = 0
new_node = Node(sum)
result = new_node

while(list2!=None):
sum = carry + list2.data
if(sum>=10):
sum = sum%10
carry = 1
else:
carry = 0
new_node = Node(sum)
result = new_node

# If carry is 1 adding it in the list
if carry ==1:
new_node = Node(carry)

prev_node = None
while current_node:
prev_node = current_node
current_node = next_node
return prev_node

print()

# Driver function
if __name__ == '__main__':
arr1 = [3,8,1,3,5]
arr2 = [6,2,4,3,5]

for i in arr1:
obj1.insert(i)

for j in arr2:
obj2.insert(j)

resultant = reverse(resultant)

Input

Linked list1: 3 8 1 3 5

Linked list2: 6 2 4 3 5

Output

### Complexity Analysis

The time complexity for this approach is - O(max(N1, N2))  because we traverse through the linked lists simultaneously, so the linked list with maximum elements will be traversed more. Nis the number of nodes in the first linked list, and N2 is the number in the second linked list.

The space complexity for this approach will be - O(max(N1, N2)), where N1 is the size of linked list1, and N2 is the size of linked list2. The resultant linked lists will be the size of the maximum between the two.

Also check out Addition of Two Numbers in Java here.

### How can you reverse a linked list?

To reverse a linked list, we start with the head node and switch the next pointer of each node to its previous node; then, we point the next of the first node to the null pointer and change the head pointer to the last node in the original list.

### How can we represent a number in the linked list?

We can represent a number using the linked list by separating all the digits of the number and assigning them to the nodes of a linked list in the same order they appear in the number. When we print the linked list nodes, they will form the number.

### How can we find the shorter linked list between two linked lists?

We can traverse through the linked lists to count the number of nodes in each and then compare them to decide which is shorter.

### Why did we reverse the linked lists in this method before finding the sum of the numbers represented by them?

We reversed the linked list to ensure that we started adding the least significant digits of the numbers represented by the linked list.

### What is a carry variable in the above method?

If the sum of two digits of a number is greater than 9, we use the carry variable to store the second digit of the sum, which is later added to the next digit of the sum.

## Conclusion

In this blog, we have discussed the linked list. We have also discussed one of the approaches to tackle the problem statement based on how to add two numbers represented by linked lists. You can check out more approaches mentioned below in the following articles.