by Given 2 numbers where each digit is represented by a Linked List, write a program to sum the numbers and save it in a third Linked List.
For eg:
List 1 = 7 -> 8 -> 6 -> 4
List 2 = 6 -> 6 -> 8 -> 4 -> 6
—————————————-
Sum = 7-> 4 -> 7 -> 1 -> 0
Let’s have a look into basic class definition for Linked List.
class LinkedList
{
public:
int data;
LinkedList* next;
LinkedList (int data);
~LinkedList ();
};
void print_linked_list (LinkedList* start)
{
if (!start)
{
cout << "Linked list is null, nothing to print" << endl;
return;
}
LinkedList* temp = start;
while (temp)
{
cout << " " << temp -> data;
temp = temp -> next;
}
cout << endl;
}
Variant 1
Most significant digit is at the beginning which means number 742 will be stored in list as 7->4->2.
Algorithm
- Find Length of List L1 (len1) and Length of List L2 (len2)
- If l1 > l2 then mark List L1 as number 1 else mark List L2 as number 1.
- Perform a traversal on List L1 till both the list are of same size.
- Call a recursive function which will reach till the end of both list and return a new node with sum of digits + carry which will be returned by the recursive function.
- At the end if carry is 1 then add a new node at the beginning if needed.
Implementation
Before going ahead let’s have a look into Linked List implementation and Linked List Length calculation. Let’s look into the sample code for summing two numbers.
LinkedList* add_number (LinkedList* l1, int l1_len, LinkedList* l2, int l2_len, int* carry)
{
if (!l1 & !l2)
return NULL;
LinkedList* l3 = NULL;
LinkedList* temp = NULL;
int sum = 0;
if (l1_len > l2_len)
{
temp = add_number (l1->next, l1_len - 1, l2, l2_len, carry);
sum = l1->data + *carry;
}
else if (l2_len = l1_len)
{
temp = add_number (l1->next, l1_len - 1, l2->next, l2_len - 1, carry);
sum = l1->data + l2->data + *carry;
}
*carry = sum / 10;
insert_at_begining (&l3, sum % 10);
l3 -> next = temp;
return l3;
}
LinkedList* add_list (LinkedList* l1, LinkedList* l2)
{
int l1_len = length_of_linked_list_using_iteration (l1);
int l2_len = length_of_linked_list_using_iteration (l2);
cout << "List 1 length: " << l1_len << "\nList 2 length: " << l2_len << endl;
int carry = 0;
LinkedList* l3 = NULL;
LinkedList* temp = NULL;
if (l1_len > l2_len)
temp = add_number (l1, l1_len, l2, l2_len, &carry);
else
temp = add_number (l2, l2_len, l1, l1_len, &carry);
if (carry)
{
insert_at_begining (&l3, carry);
l3 -> next = temp;
}
else
{
l3 = temp;
}
return l3;
}
int main ()
{
LinkedList* list1 = NULL;
insert_at_begining (&list1, 7);
insert_after_certain_element (list1, 8, 7);
insert_after_certain_element (list1, 4, 8);
insert_after_certain_element (list1, 6, 8);
LinkedList* list2 = NULL;
insert_at_begining (&list2, 6);
insert_after_certain_element (list2, 8, 6);
insert_after_certain_element (list2, 4, 8);
insert_after_certain_element (list2, 6, 4);
insert_after_certain_element (list2, 6, 6);
cout << "Number 1: ";
print_linked_list (list1);
cout << "Number 2: ";
print_linked_list (list2);
LinkedList* sum = add_list (list1, list2);
cout << "Final Sum: ";
print_linked_list (sum);
delete_all_node (&list1);
delete_all_node (&list2);
}
Let’s have a look at the output of above program.
Inserting node 8
Inserting node 4
Inserting node 6
Inserting node 8
Inserting node 4
Inserting node 6
Inserting node 6
Number 1: 7 8 6 4
Number 2: 6 6 8 4 6
List 1 length: 4
List 2 length: 5
Final Sum: 7 4 7 1 0
Variant 2
Most significant digit is at the end which means number 742 will be stored in list as 2->4->7.
Algorithm
- Call a recursive function with both List nodes and carry.
- If both list are null and
- If carry is 1 then return new node with value set to 1.
- Else return NULL
- If L1 is null
- Sum = L2 -> val + carry
- Create new node with val = SUM % 10 and next pointer pointing to return node address of same recursive function call by calling addTwoNumbersWithCarry (l1, l2->next, sum / 10);
- If L2 is null
- Sum = L1 -> val + carry
- Create new node with val = SUM % 10 and next pointer pointing to return node address of same recursive function call by calling addTwoNumbersWithCarry (l1->next, l2, sum / 10);
- Else (in this case both L1 and L2 are not null)
- Sum = l1 -> val + l2 -> val + carry;
- Create new node with val = SUM % 10 and next pointer pointing to return node address of same recursive function call by calling addTwoNumbersWithCarry (l1->next, l2->next, sum / 10);
- If both list are null and
Implementation
Let’s have a look at the sample function.
class ListNode {
public:
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
ListNode* addTwoNumbersWithCarry (ListNode* l1, ListNode* l2, int carry)
{
if (!l1 && !l2) {
if (carry) {
return new ListNode (carry);
}
return NULL;
}
int sum = 0;
if (!l1) {
sum = l2 -> val + carry;
return new ListNode (sum % 10, addTwoNumbersWithCarry (l1, l2->next, sum / 10));
} else if (!l2) {
sum = l1 -> val + carry;
return new ListNode (sum % 10, addTwoNumbersWithCarry (l1->next, l2, sum / 10));
} else {
sum = l1 -> val + l2 -> val + carry;
return new ListNode (sum % 10, addTwoNumbersWithCarry (l1->next, l2->next, sum / 10));
}
}
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
return addTwoNumbersWithCarry (l1, l2, 0);
}
