Add two numbers represented by linked lists | Set 2

Last Updated on March 9, 2022 by Ria Pathak

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

According to the problem statement, our task is to add two numbers represented by linked lists.

Constraints for this problem: You are not allowed to modify the lists.

Problem Statement Understanding

Let’s understand this problem with an example.

According to the problem statement, we will be given numbers num1 and num2 represented as a linked list, and we need to add these numbers and return the final linked list, which will be basically the linked list representation of summation of num1 and num2, i.e., linked list representation of (num1+num2).

• Firstly we have to understand how a given number is represented as a linked list, let’s say the given number is 534 then this number is represented as 5→ 3→ 4 in the form of a linked list, and when we add another number 912 (9→ 1→ 2) to this number, we will get 1446 (1→ 4→ 4→ 6).

Now I think from the above example, the problem statement is clear. So let’s see how we will approach it.

Before moving to the approach section, try to think about how you can approach this problem. If stuck, no problem, we will thoroughly see how we can approach the problem in the next section.

Let’s move to the approach section.

Approach Recursive

Let’s think, what happens when we add two numbers:

• The addition of two numbers may increase the length of the sum. The carry generated by the addition of the digits is forwarded to the left side, which may increase the length of the sum.

• Let’s understand this with an example: We are adding 375 (Three-digit number) + 852(Three-digit number) = 1227 (Four-digit number). This example shows that we need four nodes to store the summation of two three-digit numbers.

We have seen that the number of nodes in the sum list depends on the length of given numbers. Therefore, we have to think about what should be our approach when we are adding two numbers of different lengths.

There are two cases we need to handle:-

1. When both numbers are of the same length.

2. When both numbers are of different lengths.

The cases mentioned above are the two possible cases of this problem. Now, we will see how following the below steps, we can conquer this problem:

1) Calculate the size of the given linked lists.

2) If the size of the given (numbers) linked lists are the same, then calculate the sum using recursion. Hold all nodes in recursion call stack till we reach the last node, calculate the sum of last nodes and forward carry to the left side.

3) If the size of the lists is not same, then we have to follow the following steps:
a) Calculate the difference between the length of both the linked lists.
diff = (length of first linked list – length of second linked list)
b) Now, Move diff distance ahead in the linked list, which is larger in length.

• We need to move diff distances ahead in the linked list that is bigger in size because after moving diff distances ahead in the bigger linked list we have to find the sum of both linked lists that are same in length.

Let’s understand this with an example:
We are given two numbers having different lengths 43567 and 425.

• The length of the first number is 5-digit and of the second number is 3-digit.
• The difference between the length of given numbers is 2.
• So after moving 2 distances ahead in the bigger linked list, we will have to add two numbers of the same length.
  First Number: 4→ 3 →5→ 6→ 7
  Second Number: 4→ 2→ 5

c) Now use step 2 to calculate the sum of the smaller linked list and sub-list of a bigger linked list. Also, return the carry to the previous nodes.

4) Now we have the sum of the numbers (nodes) starting from head1 and head2 to the end of respective lists. (See in the above figure). But the nodes which are ignored at the beginning of the algorithm (4→ 3 in the above figure) are yet to add to the sum_list. So we will add the remaining nodes taking care of the carry.

Algorithm

Case 1

• Calculate the size of both the linked lists.
• If the size is the same, then move forward simultaneously in both lists till the last node.
• Add the last node’s data of both the linked lists, and create a new node to store this sum. This newly created node is the part of the new linked list that will store the sum of both the given list.
• Now, return the carry back to the previous nodes of the linked list to add the carry to the sum.
• Keep forwarding the carry till you reach the starting node.

Case 2

• If the size of both the lists is different, then we will find the difference between the length of both lists and store it into a variable named diff.
• Move diff distances ahead in the bigger (bigger Size) linked list.
• After moving diff length in the bigger list, calculate the sum using the algorithm of case 1.
• Now we have the sum_list linked list as sum of the two given lists.
• But one thing we have to notice is that we have to add carry to the remaining nodes of the bigger linked list which we have ignored when we moved diff distances ahead in beginning.
• After getting the sum of addition of smaller list and the right sublist of larger list (right sublist of larger list having length equal to the smaller list), if there is carry still remaining to add, then we will have to add this carry to the left remaining sublist of the larger list and also we will have to create new nodes for them and link these new nodes with sum_list.
• addCarryToRemaining() is the function used to add the carry generated from the addition of smaller list and the right sublist of larger list to the left sublist of larger list.

Dry Run

Code Implementation

#include 
using namespace std;

// Linked List Node Structure
class Node {
public:
    int data;
    Node* next;
};

typedef Node node;

void push(Node** head_ref, int newData){
    Node* new_node = new Node[(sizeof(Node))];

    new_node->data = newData;

    new_node->next = (*head_ref);

    (*head_ref) = new_node;
}

void printList(Node* node){
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
    cout << endl;
}


/* According to the algorithm we have assumed that the first number (first linked list) will be bigger in length. In case if the second number is bigger in length then swap pointer data to make the first number bigger in length. */

void swapPointer(Node** a, Node** b)
{
    node* t = *a;
    *a = *b;
    *b = t;
}

// The function to find length of the linked list
int getSize(Node* node)
{
    int size = 0;
    while (node != NULL) {
        node = node->next;
        size++;
    }
    return size;
}

// This function is to add linked list of same size
node* addSameSize(Node* head1, Node* head2, int* carry){
    if (head1 == NULL)
        return NULL;

    int sum;

    Node* result = new Node[(sizeof(Node))];

    result->next
        = addSameSize(head1->next, head2->next, carry);

    sum = head1->data + head2->data + *carry;
    *carry = sum / 10;
    sum = sum % 10;

    result->data = sum;

    return result;
}

// Using this function we are trying to add the carry from the addition of smaller list and right sublist of larger list to the left remaining sublist of the larger list
void addCarryToRemaining(Node* head1, Node* cur, int* carry,
                        Node** result)
{
    int sum;

    if (head1 != cur) {
        addCarryToRemaining(head1->next, cur, carry,
                            result);

        sum = head1->data + *carry;
        *carry = sum / 10;
        sum %= 10;

        push(result, sum);
    }
}

// This function is to find sum of both the linked list
void addList(Node* head1, Node* head2, Node** result)
{
    Node* cur;

    if (head1 == NULL) {
        *result = head2;
        return;
    }

    else if (head2 == NULL) {
        *result = head1;
        return;
    }

    int size1 = getSize(head1);
    int size2 = getSize(head2);

    int carry = 0;

    if (size1 == size2)
        *result = addSameSize(head1, head2, &carry);

    else {
        int diff = abs(size1 - size2);

        if (size1 < size2)
            swapPointer(&head1, &head2);

        for (cur = head1; diff--; cur = cur->next)
            ;

        *result = addSameSize(cur, head2, &carry);

        addCarryToRemaining(head1, cur, &carry, result);
    }

    if (carry)
        push(result, carry);
}


int main(){
    Node *head1 = NULL, *head2 = NULL, *result = NULL;

    int arr1[] = { 1, 3, 4, 5, 4};
    int arr2[] = { 5, 7, 2 };

    int size1 = sizeof(arr1) / sizeof(arr1[0]);
    int size2 = sizeof(arr2) / sizeof(arr2[0]);

    int i;
    for (i = size1 - 1; i >= 0; --i)
        push(&head1, arr1[i]);

    for (i = size2 - 1; i >= 0; --i)
        push(&head2, arr2[i]);

    addList(head1, head2, &result);

    printList(result);

    return 0;
}

class PolynomialsII
{
	class node
	{
		int val;
		node next;

		public node(int val)
		{
			this.val = val;
		}
	}
	void printlist(node head)
	{
		while (head != null)
		{
			System.out.print(head.val + " ");
			head = head.next;
		}
	}
	node head1, head2, result;
	int carry;
	/* A utility function to push a value to linked list */
	void push(int val, int list)
	{
		node newnode = new node(val);
		if (list == 1)
		{
			newnode.next = head1;
			head1 = newnode;
		}
		else if (list == 2)
		{
			newnode.next = head2;
			head2 = newnode;
		}
		else
		{
			newnode.next = result;
			result = newnode;
		}

	}
	/* Adds two linked lists of same size represented by
	 head1 and head2 and returns head of the resultant
	 linked list. Carry is propagated while returning
	 from the recursion */
	void addsamesize(node n, node m)
	{
		// Since the function assumes linked lists are of
		// same size, check any of the two head pointers
		if (n == null)
			return;

		// Recursively add remaining nodes and get the carry
		addsamesize(n.next, m.next);

		// add digits of current nodes and propagated carry
		int sum = n.val + m.val + carry;
		carry = sum / 10;
		sum = sum % 10;

		// Push this to result list
		push(sum, 3);

	}
	node cur;
	/* This function is called after the smaller list is
	added to the bigger lists's sublist of same size.
	Once the right sublist is added, the carry must be
	added to the left side of larger list to get the
	final result*/
	void propogatecarry(node head1)
	{
		// If diff. number of nodes are not traversed, add carry
		if (head1 != cur)
		{
			propogatecarry(head1.next);
			int sum = carry + head1.val;
			carry = sum / 10;
			sum %= 10;

			// add this node to the front of the result
			push(sum, 3);
		}
	}

	int getsize(node head)
	{
		int count = 0;
		while (head != null)
		{
			count++;
			head = head.next;
		}
		return count;
	}
	void addlists()
	{
		// first list is empty
		if (head1 == null)
		{
			result = head2;
			return;
		}

		// first list is empty
		if (head2 == null)
		{
			result = head1;
			return;
		}

		int size1 = getsize(head1);
		int size2 = getsize(head2);

		// Add same size lists
		if (size1 == size2)
		{
			addsamesize(head1, head2);
		}
		else
		{
			// First list should always be larger than second list.
			// If not, swap pointers
			if (size1 < size2)
			{
				node temp = head1;
				head1 = head2;
				head2 = temp;
			}
			int diff = Math.abs(size1 - size2);

			// move diff. number of nodes in first list
			node temp = head1;
			while (diff-- >= 0)
			{
				cur = temp;
				temp = temp.next;
			}

			// get addition of same size lists
			addsamesize(cur, head2);

			// get addition of remaining first list and carry
			propogatecarry(head1);
		}
			// if some carry is still there, add a new node to
			// the front of the result list. e.g. 999 and 87
			if (carry > 0)
				push(carry, 3);
		
	}
	public static void main(String args[])
	{
		PolynomialsII list = new PolynomialsII();
		list.head1 = null;
		list.head2 = null;
		list.result = null;
		list.carry = 0;
		int arr1[] = { 1, 3, 4, 5, 4 };
		int arr2[] = { 5, 7, 2 };

		
		for (int i = arr1.length - 1; i >= 0; --i)
			list.push(arr1[i], 1);

		
		for (int i = arr2.length - 1; i >= 0; --i)
			list.push(arr2[i], 2);

		list.addlists();

		list.printlist(list.result);
	}
}

Output

1 4 0 2 6

Time complexity: O(N + M), Since, we have traversed through the lists only once. N and M are the lengths of linked lists.
Space complexity: O(Maximum of N and M), Since, we have created a new list to store the sum of the given lists.

Approach Iterative

In the above approach, we have solved our problem using recursion. As we know when a program calls a function, that function goes on top of the call stack. So we can solve this question iteratively by using stack data structures to store the nodes in the stack.

As we know, we need to start adding numbers from the last of the two linked lists.

• So, we will iteratively store the nodes in the stack until we reach the end.
• After reaching the end, we will pull the nodes present on the top of both the stacks.
• After that, we will add the node’s data and create a new node for storing the sum. Store the carry for previous nodes that are stored in the stack.
• Repeat this process until both stacks got empty.

Algorithm

• Firstly, we will create two stacks from the given linked lists.
• Then, we will run a loop and store all the nodes till the end.
• Now, we will pull nodes kept at the top of both the stacks.
• Add the node’s data and create a new node for storing the sum.
• In every iteration, we will keep track of the carry.
• In the end, if carry > 0, that means we need an extra node at the start of the resultant list to accommodate this carry.

Code Implementation

#include 
using namespace std;

// Linked List Node Structure
class Node{
   public:
   int data;
   Node* next;
};

void push(Node** head_ref, int newData)
{
   Node* new_node = new Node[(sizeof(Node))];

   new_node->data = newData;

   new_node->next = (*head_ref);

   (*head_ref) = new_node;
}

// This function is to add two linked list
Node* sum_TwoList(Node* l1, Node* l2) {
   stack s1,s2;

   while(l1!=NULL){
      s1.push(l1->data);
      l1=l1->next;
   }
   while(l2!=NULL){
      s2.push(l2->data);
      l2=l2->next;
   }
   
   int carry=0;
   Node* result=NULL;
   while(s1.empty()==false || s2.empty()==false){
      int a=0,b=0;

      if(s1.empty()==false){
         a=s1.top();s1.pop();
      }

      if(s2.empty()==false){
         b=s2.top();s2.pop();
      }

      int total=a+b+carry;
      Node* temp=new Node();
      temp->data=total%10;
      carry=total/10;

      if(result==NULL){
         result=temp;
      }else{
         temp->next=result;
         result=temp;
      }

   }

   if(carry!=0){
      Node* temp=new Node();
      temp->data=carry;
      temp->next=result;
      result=temp;
   }
   return result;
}

void printList(Node *node){
   while (node != NULL){
      cout<data<<" ";
      node = node->next;
   }
   cout<= 0; --i)
      push(&head1, arr1[i]);

   for (i = size2-1; i >= 0; --i)
      push(&head2, arr2[i]);
   
   Node* sum_List = sum_TwoList(head1, head2);
   printList(sum_List);

   return 0;
}

import java.util.*;

class addTwoNumbers
{
	static class Node
    {
	    int data;
	    Node next;
	    public Node(int data)
	    {
		    this.data = data;
	    }
    }
    static Node l1, l2, result;
    public static void push(int new_data)
    {
	    Node new_node = new Node(0);
	    new_node.data = new_data;
	    new_node.next = l1;
	    l1 = new_node;
    }
    public static void push1(int new_data)
    {
	    Node new_node = new Node(0);

	    // Put in the data
	    new_node.data = new_data;

	    // Link the old list off the new node
	    new_node.next = l2;
	    l2 = new_node;
    }
    public static Node addTwo()
    {
	    Stack<Integer> stack1 = new Stack<>();
	    Stack<Integer> stack2 = new Stack<>();

	    while (l1 != null)
	    {
		    stack1.add(l1.data);
		    l1 = l1.next;
	    }
        while (l2 != null)
	    {
		    stack2.add(l2.data);
		    l2 = l2.next;
	    }
        int carry = 0;
	    Node result = null;

	    while (!stack1.isEmpty() ||!stack2.isEmpty())
	    {
		    int a = 0, b = 0;

		    if (!stack1.isEmpty())
		    {
			    a = stack1.pop();
		    }
            if (!stack2.isEmpty())
		    {
			    b = stack2.pop();
		    }
            int total = a + b + carry;
            Node temp = new Node(total % 10);
		    carry = total / 10;

		    if (result == null)
		    {   
			    result = temp;
		    }
		    else
		    {
			    temp.next = result;
			    result = temp;
		    }
	    }
        if (carry != 0)
	    {
		    Node temp = new Node(carry);
		    temp.next = result;
		    result = temp;
	    }
	    return result;
    }
    public static void printList()
    {
	    while (result != null)
	    {
		    System.out.print(result.data + " ");
		    result = result.next;
	    }
	    System.out.println();
    }
    public static void main(String[] args)
    {
	    int arr1[] = { 5, 6, 7 };
	    int arr2[] = { 1, 8 };

	    int size1 = 3;
	    int size2 = 2;

	    // Create first list as 5->6->7
	    int i;
	    for(i = size1 - 1; i >= 0; --i)
		    push(arr1[i]);

	    // Create second list as 1->8
	    for(i = size2 - 1; i >= 0; --i)
		    push1(arr2[i]);

	    result = addTwo();

	    printList();
    }
}

Output

1 4 0 2 6

Time complexity: O(N + M), Since, we have traversed through the lists only once. N and M are the lengths of linked lists.
Space complexity: O(Maximum of N and M), Since, we have created a new list to store the sum of the given lists.

So, In this blog, we have learned How to add two numbers represented by linked lists. 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.