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.

Suppose there are two linked lists such that all the nodes of theselinked 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.

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

Declare two linked lists.

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

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.

If any of the linked lists hit the nullptr, end the addition of linked lists.

Traverse the unaddressed linked list and add its data with carry.

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

Print the resultant linked list.

DRY Run

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;
}
// Function to add the linked lists.
node* addlists(struct node *head1, struct node *head2)
{
node *sumlist = nullptr;
node *curr, *last = nullptr;
int carry = 0, sum;
/*
Using a loop to add the numbers
in the nodes of both the
linked lists.
*/
/*
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
linked list.
*/
while (head1 != nullptr && head2 != nullptr)
{
sum = carry + head1->data + head2->data;
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 (head1)
{
head1 = head1->next;
}
if (head2)
{
head2 = head2->next;
}
}
/*
Adding if any remaining elements in the linked list1.
*/
while (head1 != nullptr)
{
sum = carry + head1->data;
if (sum >= 10)
{
sum = sum % 10;
carry = 1;
}
else
{
carry = 0;
}
curr = createnode(sum);
last->next = curr;
last = curr;
head1 = head1->next;
}
/*
Adding if any remaining elements in the linked list2.
*/
while (head2 != nullptr)
{
sum = carry + head2->data;
if (sum >= 10)
{
sum = sum % 10;
carry = 1;
}
else
{
carry = 0;
}
curr = createnode(sum);
last->next = curr;
last = curr;
head2 = head2->next;
}
/*
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.
node* reverse(node *head)
{
// If the list is empty or contains a single node.
if (head == nullptr || head->next == nullptr)
{
return head;
}
// Reversing the list.
node *headrev = reverse(head->next);
head->next->next = head;
head->next = nullptr;
// Returning the head pointer.
return headrev;
}
// 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.
newnode->next = (*headr);
// Shifting the head pointer to a new node.
*headr = newnode;
}
// Driver function.
int main()
{
node *head1 = nullptr;
node *head2 = nullptr;
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;
push(&head1, 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;
push(&head2, a);
}
cout << endl;
// Calling the addition function.
struct node *sumlist = addlists(head1, head2);
// Reversing the resultant linked list.
sumlist = reverse(sumlist);
// Printing the final linked list.
cout << "Resultant Linked List:";
while (sumlist != nullptr)
{
cout << sumlist->data << " ";
sumlist = sumlist->next;
}
return 0;
}

You can also try this code with Online C++ Compiler

Thetime complexity for this approach is - O(max(N_{1}, N_{2})) because we traverse through the linked lists simultaneously, so the linked list with maximum elements will be traversed more. N_{1 }is the number of nodes in the first linked list, and N_{2} is the number in the second linked list.

Thespace complexity for this approach will be - O(max(N_{1}, N_{2})), 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.

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.