Add Two Numbers Represented by the Linked Lists | Part-1

Brute Force Approach

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

1. Declare two linked lists.
    
2. Traverse through both linked lists with one node at a time, start with the least significant digits of the number.
    
3. 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.
    
4. If any of the linked lists hit the nullptr, end the addition of linked lists.
    
5. Traverse the unaddressed linked list and add its data with carry.
    
6. Add an extra node into the linked list if carry after the last node is 1.
    
7. 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

Run Code

Output

Implementation in Python

# Creating the node
class Node:
    def __init__(self,data):
        self.data = data
        self.nextAddress = None
 
# Creating the linked lists of nodes
class Createlinkedlist:
    def __init__(self):
        self.head = None
    
    def insert(self, data):
       
       newNode = Node(data)
       
       if self.head is None:
           self.head = newNode
       else:
           newNode.nextAddress = self.head
           self.head = newNode

class AddLinkedLists:
    def __init__(self):
        self.head = None
        
    # Function to add the numbers     
    def addnumbers(self,list1,list2):
        result = None
        carry = 0
        while(list1!=None and list2!=None):
            sum = carry + list1.data + list2.data
            if(sum>=10):
                carry = 1
            else:
                carry = 0
            list1 = list1.nextAddress
            list2 = list2.nextAddress
            
            # Adding the sum in resultant linked list
            new_node = Node(sum%10)
            if self.head is None:
                self.head = new_node
                result = new_node
            else:
                result.nextAddress = new_node
                result = new_node
                
        while(list1!=None):
            sum = carry + list1.data
            if(sum>=10):
                sum = sum%10
                carry = 1
            else:
                carry = 0
            new_node = Node(sum)
            result.nextAddress = new_node
            result = new_node
            list1 = list1.nextAddress
        
        while(list2!=None):
            sum = carry + list2.data
            if(sum>=10):
                sum = sum%10
                carry = 1
            else:
                carry = 0
            new_node = Node(sum)
            result.nextAddress = new_node
            result = new_node
            list2 = list2.nextAddress
            
        # If carry is 1 adding it in the list    
        if carry ==1:
            new_node = Node(carry)
            result.nextAddress = new_node
                
        return self.head

# Reversing the linked lists        
def reverse(reversehead):
        prev_node = None
        current_node = reversehead
        while current_node:
            next_node = current_node.nextAddress
            current_node.nextAddress = prev_node
            prev_node = current_node
            current_node = next_node
        return prev_node

# Printing the linked lists
def printlinkedlist(head):
    while head is not None:
        print(head.data,end=' ')
        head = head.nextAddress
    
    print()
 
# Driver function
if __name__ == '__main__':
    arr1 = [3,8,1,3,5]
    arr2 = [6,2,4,3,5]
    
    obj1 = Createlinkedlist()
    for i in arr1:
        obj1.insert(i)
    
    obj2 = Createlinkedlist()
    for j in arr2:
        obj2.insert(j)
    
    obj3 = AddLinkedLists()
    
    resultant = obj3.addnumbers(obj1.head,obj2.head)
    resultant = reverse(resultant)
    print("resultant linkedlist: ")
    printlinkedlist(resultant)

You can also try this code with Online Python Compiler

Run Code

Input

Linked list1: 3 8 1 3 5

Linked list2: 6 2 4 3 5

Output

Complexity Analysis

The time complexity for this approach is - O(max(N₁, N₂))  because we traverse through the linked lists simultaneously, so the linked list with maximum elements will be traversed more. N₁ is the number of nodes in the first linked list, and N₂ is the number in the second linked list. 

The space complexity for this approach will be - O(max(N₁, N₂)), 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.

Also check out Addition of Two Numbers in Java here.

Frequently Asked Questions

How can you reverse a linked list?

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.

Recommended Reading:

• Add Two Numbers Represented by Linked Lists | Part 2
• Add Two Numbers Represented by Linked Lists | Part 3
• Point to the next higher node in Linked List
• Largest and Smallest Element in a Singly Linked List
• Advantages and Disadvantages of Linked List
   

Check out the Interview guide for Product-Based Companies and some of the popular interviews.

Problems from top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also, check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, and System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top industry experts only on Coding Ninjas Studio.

Happy Coding!