Do you think IIT Guwahati certified course can help you in your career?
No
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.
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
Take the user input for both linked lists.
Find the sizes of the linked list to find the larger linked list.
We reverse the linked lists so that the pointers point to the least significant digit of the number they represent.
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.
After traversing the shorter linked list, we put zero in place of the value of its node.
Add an extra node into the linked list if carry after the last node is 1.
Return the larger linked list as the resultant and reverse it.
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) {
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
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
#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
Thetime complexity for this approach is - O(NL) because the maximum number of nodes we traverse in a loop will be NL, where NL is the number of nodes in the larger linked list.
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.