Add two numbers represented by linked lists | Set 1

Problem Statement

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.

Problem Statement Understanding:

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

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 the given problem. Try to think of an approach to solve it.

Now, let us look at how to approach it.

Approach 1 (Converting the two linked lists to integers)

To add two numbers, 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:
1) To reverse a linked list.
2) To convert linked list to integers.
3) To convert an integer to a linked list.

Algorithm

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.
ans = to_linkedlist(sum).
4) 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 solve it, before moving to the implementation try to implement it yourself.

Dry Run

Code Implementation

#include
using namespace std;

struct Node {
    int val;
    Node* next;

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

void push_front(Node** head, int new_val){
    Node* new_node = new Node(new_val);
    new_node->next = *head;
    *head = new_node;
}

void printList(Node* head){
    Node* i = head;
    while(i){
        cout<val<<" ";
        i = i->next;
    }
    cout<<"\n";
}

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

// function to convert a linked list to integer
int to_integer(Node* head){
    int num = 0;
    Node* curr = head;
    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
Node* to_linkedlist(int x){
    Node* head = new Node(0);
    if(x==0) return head;


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

// function to add 2 numbers given as linked lists
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
    // a linked list
    Node* ans = to_linkedlist(sum);
    
    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

    Node* sum = add_list(l1,l2);

    printList(sum);
    // 2 1 4
}

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 number is huge eg., 30? Then the above approach would fail and we need to improve upon it.

Approach 2 (Simple iteration with 2 pointers)

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.

Algorithm

1) Use 2 pointers to store the head of each linked list and initialize carry as 0.
2) Declare a pointer to 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 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.

Dry Run

Code Implementation:




#include
using namespace std;

struct Node {
    int val;
    Node* next;

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

void push_front(Node** head, int new_val){
    Node* new_node = new Node(new_val);
    new_node->next = *head;
    *head = new_node;
}

void printList(Node* head){
    Node* i = head;
    while(i){
        cout<val<<" ";
        i = i->next;
    }
    cout<<"\n";
}

// function to add 2 numbers given as linked lists
Node* add(Node* l1, Node* l2){
    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

    Node* sum = add(l1,l2);

    printList(sum);
    // 2 1 4      = 412
}

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.

In this blog, we have seen how to add two numbers represented as linked lists by using two different methods. Problems like these are good for strengthening your concepts in LinkedList. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Delete nodes that have a greater value on the right side
Next post Print Reverse Of A Linked List Without Actually Reversing it

Leave a Reply

Your email address will not be published. Required fields are marked *