Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
In this article at OpenGenus, we will add numbers stored in a linked list data structure and implement it in C++ Programming Language.
Table of contents:
- Introduction to the problem statement
- Properties of a linked list data structure
- Pseudo code
- Tracing the solution
- Implementing the solution
- Time and space complexity
Introduction to the problem statement
Given two linked lists representing two numbers, each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
Properties of a linked list data structure
Each node in the list contains two parts:
i. the data part : Stores the value
ii. a reference (or pointer) : points to the next node in the sequence.
The head initially points to NULL for all lists. When the values are added, for each linked list, it points to the first node.
Pseudo code
Function addTwoNumbers(list1, list2):
Create a result LinkedList to store the sum of the two input linked lists.
Create a movable pointer l1, l2 for both list1 and list2 respectively.
Initialize variable carry to 0
While l1 pointer is not NULL OR l2 pointer is not NULL OR carry is not 0:
If l1 is not NULL:
Add the value of list1 to sum
Move l1 to the next node
If l2 is not NULL:
Add the value of list2 to sum
Move l2 to the next node
Add the carry to sum
Set carry to sum divided by 10
Create a new node using add function with value (sum mod 10)
Return the result
Tracing the solution
Let's break down each part of the code:
i. Node class
This class represents a single node in a linked list. It has two members:
- val : to store the value of the node and,
- next : to point to the next node in the list.
The constructor initializes val with the given value and sets next to point to NULL.
class Node {
public:
int val;
Node* next;
Node(int value) : val(value), next(NULL) {}
};
ii. LinkedList class
This class contains the following :
- head node : The head node is initialised to NULL when the linked lists are created. It is used to point to the starting node of a linked list while appending values into the linked lists.
private:
Node* head;
public:
LinkedList() : head(NULL) {}
- add method : The add method appends input values to the end of the specified linked list. A new node is created and assigned the input value. If the list is empty, i.e., if head is NULL, the head points to the new node and returns.
In case the list is already filled, we traverse to the end of the list, and append the new node.
void add(int value)
{
Node* node = new Node(value);
if (head == NULL)
{
head = node;
return;
}
Node* temp = head;
while (temp->next != NULL)
{
temp = temp->next;
}
temp->next = node;
node->next = NULL;
}
- addTwoNumbers method : The method takes two linked lists (list1 and list2) representing non-negative integers and returns a new linked list, result, representing their sum. Two pointers, l1 pointing to list1 and l2 pointing to list2 are created to keep track of the two lists. Also, we use a carry variable to handle carry operation during addition.
Node* l1 = list1.head;
Node* l2 = list2.head;
int carry = 0;
A while loop iterates through lists simultaneously until both linked lists become NULL and the carry, 0 . It calculates the sum of corresponding digits from l1 and l2, adds carry if any, updates the carry for the next iteration, adds a new node to the end of result, with the sum modulo 10. It also moves the pointers l1 and l2 to the next nodes in their respective lists.
while (l1 != NULL || l2 != NULL || carry)
{
int sum = 0;
if(l1 != NULL)
{
sum += l1->val;
l1 = l1->next;
}
if(l2 != NULL)
{
sum += l2->val;
l2 = l2->next;
}
sum += carry;
carry = sum / 10;
result.add(sum % 10);
}
return result;
- printList method : Finally, we print the result of the two lists.
This function is used to print the elements of a linked list. It takes a pointer to the head of the list as input and traverses the list, printing each element's value.
Node* temp = head;
while (temp != NULL)
{
std::cout<<temp->val<<" ";
temp = temp->next;
}
iii. main function
In the main function, we create two linked lists list1 and list2 representing the numbers to be added. Then, we call the addTwoNumbers method of the LinkedList class to get the result as a new linked list result.
// Create two linked lists
LinkedList list1;
LinkedList list2;
// Add to list1 : 321
list1.add(1);
list1.add(2);
list1.add(3);
// Add to list2: 765
list2.add(5);
list2.add(6);
list2.add(7);
Implementing the solution
#include <iostream>
class Node {
public:
int val;
Node* next;
Node(int value) : val(value), next(NULL) {}
};
class LinkedList {
private:
Node* head;
public:
LinkedList() : head(NULL) {}
void add(int value)
{
Node* node = new Node(value);
if (head == NULL)
{
head = node;
return;
}
Node* temp = head;
while (temp->next != NULL)
{
temp = temp->next;
}
temp->next = node;
node->next = NULL;
}
static LinkedList addTwoNumbers(LinkedList list1, LinkedList list2)
{
LinkedList result;
Node* l1 = list1.head;
Node* l2 = list2.head;
int carry = 0;
while (l1 != NULL || l2 != NULL || carry)
{
int sum = 0;
if(l1 != NULL)
{
sum += l1->val;
l1 = l1->next;
}
if(l2 != NULL)
{
sum += l2->val;
l2 = l2->next;
}
sum += carry;
carry = sum / 10;
result.add(sum % 10);
}
return result;
}
void printList() {
Node* temp = head;
while (temp != NULL)
{
std::cout<<temp->val<<" ";
temp = temp->next;
}
}
};
int main() {
// Create two linked lists
LinkedList list1;
LinkedList list2;
// Add to list1 : 321
list1.add(1);
list1.add(2);
list1.add(3);
// Add to list2: 765
list2.add(5);
list2.add(6);
list2.add(7);
// Add the two lists
LinkedList result;
result = LinkedList::addTwoNumbers(list1, list2);
// Display the result
std::cout<<"Sum: ";
result.printList();
return 0;
}
Let's trace the above program with an example where we add the numbers 321 and 765, which are represented by the following linked lists:
list1: 1 -> 2 -> 3 -> NULL
list2: 5 -> 6 -> 7 -> NULL
Now, let's trace the addTwoNumbers function:
We start with 2 list pointers, l1 pointing to list1 and l2 pointing to list2.
Iteration 1:
l1 points to 1, l2 points to 5, and carry is 0.
The sum is 1 + 5 + 0 = 6, so we add a new node with value 6 to the result linked list.
Move l1 and l2 to their next nodes.
Iteration 2:
l1 points to 2, l2 points to 6, and carry is 0.
The sum is 2 + 6 + 0 = 8, so we append a new node with value 8 to the result linked list.
Move l1 and l2 to their next nodes.
Iteration 3:
l1 points to 3, l2 points to 7, and carry is 0.
The sum is 3 + 7 + 0 = 10, so we append a new node with value 0 to the result linked list(least significant bit is 0) and carry is 1.
Move l1 and l2 to their next nodes.
Iteration 4:
l1 is NULL, l2 is NULL, and carry is 1.
The sum is 0 + 0 + 1 = 1, so we append a new node with value 1 to the result linked list.
Iteration 5:
Since both lists are NULL and there's no carry, we exit the loop.
We return the result linked list to be printed.
So, the resulting linked list representing the sum of 321 and 765 is:
Result: 6 -> 8 -> 0 -> 1 -> NULL
This linked list represents the number 1086.
Time and space complexity
Time complexity
Within each iteration of the loop, the operations performed are constant time. Therefore, the overall time complexity is determined by the maximum length of the input linked lists.
Time Complexity: O(max(N, M))
Space complexity
The overall space complexity is determined by the maximum length of the input linked lists.
Space Complexity: O(max(N, M))
