Table of contents
1.
Introduction
2.
Problem Statement
3.
Space Efficient Approach
3.1.
Algorithm
3.2.
DRY Run
3.3.
Implementation in C++
3.4.
Implementation in Java
3.5.
Implementation in Python
3.6.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
Do linked lists need pre-allocated memory like arrays?
4.2.
How to insert operations in an array is different from the insert operation in a linked list.
4.3.
What are the disadvantages of using linked lists?
4.4.
Mention a few applications on the linked list.
4.5.
What is cache locality? And which has better cache locality among arrays and linked lists?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

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

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

In the previous blogs on adding two numbers represented by linked lists, we discussed and implemented two approaches. First, we add the nodes of both the linked list one by one simultaneously by adding preceding zeroes to the shorter linked list, and in another approach, we use stacks to add two numbers represented by the linked lists. 

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

In this blog, we will now learn about the space-efficient approach, which takes constant space to add two numbers represented by the linked lists, but before diving into the solution, let's briefly discuss the problem again.

Problem Statement

The problem states there are two linked lists such that all the nodes of these linked lists contain numbers between 1 to 9. Now we are asked to find the sum of the numbers formed by these linked lists treating nodes as the digits of a number. 

For example,

Input

Numbers of Nodes in linked list 1 and 2: 4 3

Nodes in linked list 1: 3 -> 4 -> 2 -> 6 

Nodes in linked list 2: 7 -> 3 -> 2

Output

4 -> 1 -> 5->8

Space Efficient Approach

This approach aims to add two numbers represented by the linked lists in constant space. For this, rather than storing the sum in a separate linked list, we modify the larger linked list to store the sum and return it as the resultant linked list. 

We start with finding the larger linked list, then traverse through the linked lists and store the sum for each pair of nodes and the carry from the previous nodes in the nodes of the larger linked list. 

We replace the value of the shorter linked list's nodes with zeroes for the addition if we have traversed through all of its nodes. And once we are done traversing the larger linked list, we check for the carry; if it is one, we add one as an extra node to the larger linked list. And return it as the resultant linked list. 

Algorithm

  1. Take the user input for both linked lists.
     
  2. Find the sizes of the linked list to find the larger linked list.
     
  3. We reverse the linked lists so that the pointers point to the least significant digit of the number they represent.
     
  4. Then, we add each pair of nodes corresponding to the same place value in the number, along with the carry from the previous pair. And replace the node of the larger linked list with the sum.
     
  5. After traversing the shorter linked list, we put zero in place of the value of its node. 
     
  6. Add an extra node into the linked list if carry after the last node is 1.
     
  7. Return the larger linked list as the resultant and reverse it.
     
  8. Print the resultant linked list.

DRY Run

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) {
	int carry = 0, sum;
	/*
		Create a temporary variable to traverse through the larger linked list.
	*/
	node *temp = head2;
	
	/*
		Temporary node to store the last modified node.
	*/
	node *last = nullptr;
	
	/*
		Using a loop to add the numbers in the nodes of both the linked lists.
		
		To calculate the sum of 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 sum is greater than 10 then will take carry=sum/10 and
		add the sum%10 in the resultant.
	*/
	while (temp != nullptr) {
		sum = carry + (head1 ? head1->data : 0) + temp->data;

		carry = (sum >= 10) ? 1 : 0;

		sum = sum % 10;
		temp->data = sum;

		last = temp;

		if (temp) {
			temp = temp->next;
		}

		if (head1) {
			head1 = head1->next;
		}
	}

	/*
	    If we are left only with a carry in the last, 
	    we create a new node with it and append it.
	*/
	if (carry > 0) {
		struct node *car = createnode(carry);
		last->next = car;
	}

	// Returning the head of the larger linked list.
	return head2;
}

// Function to reverse the linked lists.
node* reverse(node *head) {
	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 of the reversed linked list.
	*/
	return headrev;
}

// Function to push nodes into the list.
void push(struct node **headr, int newval) {
	struct node *newnode = createnode(newval);
	newnode->next = (*headr);
	*headr = newnode;
}

// Driver function.
int main() {
	node *head1 = nullptr;
	node *head2 = nullptr;
	// linkedlist1 elements
     push(&head1,3);
     push(&head1,4);
     push(&head1,2);
     push(&head1,6);
     
    // linkedlist2 elements
    push(&head2,7);
    push(&head2,3);
    push(&head2,2);

	struct node* sumlist;
    /*
        Calling the addition function.
        Passing the largest Linkedlist as the second argument.
    */
        sumlist= addlists(head2, head1);

	// Reversing the resultant linked list.
	sumlist = reverse(sumlist);

	// Printing the resultant 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

c++ program output

Implementation in Java

import java.util.*;

class Node {
    int data;
    Node next;

    // Constructor
    Node(int d) {
        data = d;
        next = null;
    }
}

class LinkedList {
    Node head;

    // Helper function to Print
    void Print(Node head) {
        while (head != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }
    }

    /* 
         Function to add data in the linked list
    */
    void insert(int x) {
        Node temp = new Node(x);
        if (head == null) head = temp;
        else {
            temp.next = head;
            head = temp;
        }
    }

    /* 
         Helper function to reverse the list
    */
    public static Node reverse(Node head) {
        if (head == null || head.next == null) return head;

        Node prev = null;
        Node curr = head;
        while (curr != null) {
            Node temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }
        head = prev;
        return head;
    }

    // Function to add two lists
    public static Node sum(Node l1, Node l2) {
        if (l2 == null) return l1;
        if (l1 == null) return l2;

        /*
             storing head of those linked list
             whose reverse is to be returned
        */
        Node head = l1;
        Node prev = null;
        int c = 0, sum;
        while (l1 != null && l2 != null) {
            sum = c + l1.data + l2.data;
            l1.data = sum % 10;
            c = sum / 10;
            prev = l1;
            l1 = l1.next;
            l2 = l2.next;
        }

        if (l1 != null || l2 != null) {
            if (l2 != null) prev.next = l2;
            l1 = prev.next;
            while (l1 != null) {
                sum = c + l1.data;
                l1.data = sum % 10;
                c = sum / 10;
                prev = l1;
                l1 = l1.next;
            }
        }
        if (c > 0) prev.next = new Node(c);
        return reverse(head);
    }
}

/*
	Driver Main Class
*/
class Main {
    public static void main(String[] args) {
        // Linkedlist1 elements
		LinkedList l1 = new LinkedList();
		l1.insert(3);
		l1.insert(4);
		l1.insert(2);
		l1.insert(6);
       
		// Linkedlist2 elements
		LinkedList l2 = new LinkedList();
		l2.insert(7);
		l2.insert(3);
		l2.insert(2);
        LinkedList l3 = new LinkedList();
        Node head = l3.sum(l1.head, l2.head);
        System.out.print("Resultant Linked list: ");
        l3.Print(head);
    }
}
You can also try this code with Online Java Compiler
Run Code


Output

java code output


Also check out Addition of Two Numbers in Java here.

Implementation in Python

#Structure for a node in the linked list.
class Node:
   
   def __init__(self, data):
       
       self.data = data
       self.next = None

# Handle all List operations
class LinkedList:
   
   def __init__(self):
       
       self.head = None

   # Method to Print list
   def Print(self):
       
       linkedListStr = ""
       temp = self.head
       
       while temp:
           linkedListStr += str(temp.data)+" "
           temp = temp.next
           
       return linkedListStr

   # Method to insert data in linked list
   def insert(self, data):
       
       newNode = Node(data)
       
       if self.head is None:
           self.head = newNode
       else:
           newNode.next = self.head
           self.head = newNode

# Helper function to reverse the list
def reverse(Head):
   
   if (Head is None and
       Head.next is None):
       return Head
       
   prev = None
   curr = Head
   
   while curr:
       temp = curr.next
       curr.next = prev
       prev = curr
       curr = temp
       
   Head = prev
   return Head

# Function to add two lists
def listSum(l1, l2):

   if l1 is None:
       return l1
   if l2 is None:
       return l2

   # Storing head whose reverse
   # is to be returned This is
   # where which will be final node
   head = l1
   prev = None
   c = 0
   sum = 0
   
   while l1 is not None and l2 is not None:
       sum = c + l1.data + l2.data
       l1.data = sum % 10
       c = int(sum / 10)
       prev = l1
       l1 = l1.next
       l2 = l2.next
       
   if l1 is not None or l2 is not None:
       if l2 is not None:
           prev.next = l2
       l1 = prev.next
       
       while l1 is not None:
           sum = c + l1.data
           l1.data = sum % 10
           c = int(sum / 10)
           prev = l1
           l1 = l1.next
           
   if c > 0:
       prev.next = Node(c)
       
   return reverse(head)
   
# Driver code

# Inserting Linkedlist1 elements
linkedList1 = LinkedList()
linkedList1.insert(3)
linkedList1.insert(4)
linkedList1.insert(2)
linkedList1.insert(6)

# Inserting Linkedlist2 elements
linkedList2 = LinkedList()
linkedList2.insert(7)
linkedList2.insert(3)
linkedList2.insert(2)

linkedList3 = LinkedList()
linkedList3.head = listSum(linkedList1.head,
                          linkedList2.head)
                           
print("Resultant Linked list: ")
print(linkedList3.Print())

You can also try this code with Online Python Compiler
Run Code


Output

python code output

Complexity Analysis

The time complexity for this approach is - O(NL)  because the maximum number of nodes we traverse in a loop will be  NL, where Nis the number of nodes in the larger linked list. 

The space complexity for this approach will be - O(1).

Must Read Python List Operations

Frequently Asked Questions

Do linked lists need pre-allocated memory like arrays?

No, linked lists don't need pre-allocated memory during declaration. Rather we use dynamic memory location in the case of linked lists.

How to insert operations in an array is different from the insert operation in a linked list.

Insert operation in an array might need to shift a few elements to make space for the new element, as the memory allocation is contiguous in arrays. In contrast, in the linked list, we can insert a new node in the linked without shifting any element.

What are the disadvantages of using linked lists?

It does not allow random access to elements, and we can not traverse through a linked list in the reverse direction.

Mention a few applications on the linked list.

Applications of linked lists involve the implementation of stacks and queues and storing adjacency lists in case of implementation of graphs. 

What is cache locality? And which has better cache locality among arrays and linked lists?

Cache locality refers to the tendency of future operations to be available in the cache. In arrays, all elements are in contiguous memory locations. Thus it has better cache locality than linked lists.

Conclusion

This blog discussed the space-efficient approach to adding two numbers represented by the linked lists. We have discussed the problem statement with the help of a visual demonstration. We have also implemented the problem in three coding languages.

Recommended Reading:


Do check out The Interview guide for Product Based Companies, as well as some of the popular interview problems, asked in 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, 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!

Live masterclass