Subtract Two Numbers Represented as Linked Lists

Last Updated on November 8, 2022 by Sumit Kumar

We already have an idea as we have solved many operations that can be performed on the linked list. In this article, we will subtract two numbers represented as linked lists. We have given two lists and we have to subtract two numbers represented as linked lists.

How to Subtract Two Numbers as Linked Lists

In this problem, we are given two linked lists, L1 and L2. Both L1 and L2 are positive numbers represented as linked lists. Our task is to subtract the smaller lists from the larger list (smaller and larger value-wise) and return the difference between the values of the list as a linked list.

One thing that we have to note is that the input lists can be in any order, but we always need to subtract the smaller list from the larger list. It may be assumed that there are no leading zeroes in the input lists.

Understanding with Example

Let’s try to understand this problem with the help of examples.

If the list given to us be L1 = 1 → 0 → 0 → NULL and L2 = 5 → NULL.

According to the problem statement, we need to subtract the smaller list from the larger list and return the difference in form of a list.
From the input, we can clearly see that the list L1 is greater than the list L2, so we will have to subtract the list L2 from list L1.
The numeric representation of list L1 is 100, and list L2 is 5. The difference between L1 and L2 is 95.
Our output will be the linked list representation of the difference between L1 and L2, which will be 0 → 9 → 5 → NULL.

Let’s take another example to make the problem understanding more clearer. If the given lists are L1 = 5 → 2 → 3 →NULL and L2 = 6 → 3 → 5 → NULL.

In this case, we can clearly see that list L2 is greater than list L1 (value wise) and the numeric difference between L2 and L1 is 635 – 523 = 112.
Now our output will be the linked list representation of the difference between the numeric representation of L1 and L2, which will be 1 → 1 → 2 → NULL.

Some more examples

Sample Input 1:

Sample Output 1:

Sample Output 2: L1 = 1→2→5→6→NULL, L2 = 3→4→NULL

Sample Output 2: 1→2→2→2→NULL

Now, I think from the above examples, the problem statement is clear. Let’s see how we can 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 this problem in the next section.

Let’s move to the approach section.

Approach to subtract two numbers represented as linked lists

Our approach will be simple:

First, we have to find the greater value list among the given lists.
How we will do that:
- If sizes of lists are different, then we know which linked list is smaller, and we’ll proceed by appending zeroes at the end of the smaller linked list.
- If the sizes of the lists are the same, then we will find the numerical values represented by both the linked lists and find the smaller linked list.
After this, we will, one by one, subtract nodes of the smaller linked list from the larger list.

Let’s move to the algorithm section

Algorithm to subtract two numbers represented as linked lists

Calculate the size of the given two linked lists.
- If sizes are not the same, append zeroes in the smaller linked list using paddZeros function.
- If sizes are the same, then we have to find the smaller value linked list.
Now that we know which linked list is smaller, we follow the below steps:
- We have to one by one subtract the nodes of the smaller linked list from the larger linked list.
- We also have to keep track of borrow while subtracting.
Once we are done substracting, we will have our difference of L1 and L2 in form of linked list.

Dry Run for subtracting 2 numbers

Code Implementation to Subtract 2 Numbers Represented as Linked Lists

C++
Java

#include 
using namespace std;
 
/* Node structure of a singly linked list */
struct Node {
    int data;
    struct Node* next;
};

/* Using this function we will create a new node and return it */
Node* newNode(int data)
{
    Node* temp = new Node;
    temp->data = data;
    temp->next = NULL;
    return temp;
}

/* Using this function we will find the length of a linked list */
int findLength(Node* Node)
{
    int size = 0;
    while (Node != NULL) {
        Node = Node->next;
        size++;
    }
    return size;
}
 
/* Using this function we will be padding the smaller list (list having smaller length among the given two lists) with nodes having data = 0 */
Node* paddZeros(Node* sNode, int diff)
{
    if (sNode == NULL)
        return NULL;
 
    Node* zHead = newNode(0);
    diff--;
    Node* temp = zHead;
    while (diff--) {
        temp->next = newNode(0);
        temp = temp->next;
    }
    temp->next = sNode;
    return zHead;
}
 
/* Using this helper function we will substract the two given linked lists and will retur their difference in form of a linked list */
Node* SubtractHelper(Node* l1, Node* l2, bool& borrow)
{
    if (l1 == NULL && l2 == NULL && borrow == 0)
        return NULL;
 
    Node* previous
        = SubtractHelper(
            l1 ? l1->next : NULL,
            l2 ? l2->next : NULL, borrow);
 
    int d1 = l1->data;
    int d2 = l2->data;
    int sub = 0;
 
    if (borrow) {
        d1--;
        borrow = false;
    }
 
    if (d1 < d2) {
        borrow = true;
        d1 = d1 + 10;
    }
 
    sub = d1 - d2;
 
    Node* current = newNode(sub);
 
    current->next = previous;
 
    return current;
}
 
/* Main function for substraction of linked lists */
Node* subtractLinkedList(Node* l1, Node* l2)
{
    if (l1 == NULL && l2 == NULL)
        return NULL;
    
    int lenLst1 = findLength(l1);
    int lenLst2 = findLength(l2);
 
    Node *largerListNode = NULL, *smallerListNode = NULL;
 
    Node* temp1 = l1;
    Node* temp2 = l2;

    if (lenLst1 != lenLst2) {
        largerListNode = lenLst1 > lenLst2 ? l1 : l2;
        smallerListNode = lenLst1 > lenLst2 ? l2 : l1;
        smallerListNode = paddZeros(smallerListNode, abs(lenLst1 - lenLst2));
    }
 
    else {
        while (l1 && l2) {
            if (l1->data != l2->data) {
                largerListNode = l1->data > l2->data ? temp1 : temp2;
                smallerListNode = l1->data > l2->data ? temp2 : temp1;
                break;
            }
            l1 = l1->next;
            l2 = l2->next;
        }
    }
 
    
    bool borrow = false;
    return SubtractHelper(largerListNode, smallerListNode, borrow);
}
 
/* Using this function we will be printing the content of the linked list */
void printList(struct Node* Node)
{
    while (Node != NULL) {
        printf("%d ", Node->data);
        Node = Node->next;
    }
    printf("\n");
}
 

int main()
{
    Node* L1 = newNode(1);
    L1->next = newNode(3);
    L1->next->next = newNode(5);
    L1->next->next->next = newNode(7);
    cout<<"Linked list 1: "<next = newNode(5);
    L2->next->next = newNode(8);
    cout<<"Linked list 2: "<

class Substract 
{
	static Node head; 
	boolean borrow;
	static class Node 
    {
		int data;
		Node next;
		Node(int d)
		{
			data = d;
			next = null;
		}
	}
	/* A utility function to get length of linked list */
	int getLength(Node node)
	{
		int size = 0;
		while (node != null) {
			node = node.next;
			size++;
		}
		return size;
	}
	/* A Utility that padds zeros in front
	of the Node, with the given diff */
	Node paddZeros(Node sNode, int diff)
	{
		if (sNode == null)
			return null;

		Node zHead = new Node(0);
		diff--;
		Node temp = zHead;
		while ((diff--) != 0) {
			temp.next = new Node(0);
			temp = temp.next;
		}
		temp.next = sNode;
		return zHead;
	}
	/* Subtract LinkedList Helper is a recursive
	function, move till the last Node, and
	subtract the digits and create the Node and
	return the Node. If d1 < d2, we borrow the
	number from previous digit. */
	Node subtractLinkedListHelper(Node l1, Node l2)
	{
		if (l1 == null && l2 == null && borrow == false)
			return null;

		Node previous
			= subtractLinkedListHelper(
				(l1 != null) ? l1.next
							: null,
				(l2 != null) ? l2.next : null);

		int d1 = l1.data;
		int d2 = l2.data;
		int sub = 0;

		/* if you have given the value to
		next digit then reduce the d1 by 1 */
		if (borrow) {
			d1--;
			borrow = false;
		}

		/* If d1 < d2, then borrow the number from
		previous digit. Add 10 to d1 and set
		borrow = true; */
		if (d1 < d2) {
			borrow = true;
			d1 = d1 + 10;
		}

		/* subtract the digits */
		sub = d1 - d2;

		/* Create a Node with sub value */
		Node current = new Node(sub);

		/* Set the Next pointer as Previous */
		current.next = previous;

		return current;
	}
	/* This API subtracts two linked lists and
	returns the linked list which shall have the
	subtracted result. */
	Node subtractLinkedList(Node l1, Node l2)
	{
		// Base Case.
		if (l1 == null && l2 == null)
			return null;

		// In either of the case, get the lengths
		// of both Linked list.
		int len1 = getLength(l1);
		int len2 = getLength(l2);

		Node lNode = null, sNode = null;

		Node temp1 = l1;
		Node temp2 = l2;

		// If lengths differ, calculate the smaller
		// Node and padd zeros for smaller Node and
		// ensure both larger Node and smaller Node
		// has equal length.
		if (len1 != len2) {
			lNode = len1 > len2 ? l1 : l2;
			sNode = len1 > len2 ? l2 : l1;
			sNode = paddZeros(sNode, Math.abs(len1 - len2));
		}

		else {
			// If both list lengths are equal, then
			// calculate the larger and smaller list.
			// If 5-6-7 & 5-6-8 are linked list, then
			// walk through linked list at last Node
			// as 7 < 8, larger Node is 5-6-8 and
			// smaller Node is 5-6-7.
			while (l1 != null && l2 != null) {
				if (l1.data != l2.data) {
					lNode = l1.data > l2.data ? temp1 : temp2;
					sNode = l1.data > l2.data ? temp2 : temp1;
					break;
				}
				l1 = l1.next;
				l2 = l2.next;
			}
		}
		// After calculating larger and smaller Node,
		// call subtractLinkedListHelper which returns
		// the subtracted linked list.
		borrow = false;
		return subtractLinkedListHelper(lNode, sNode);
	}
	static void printList(Node head)
	{
		Node temp = head;
		while (temp != null) {
			System.out.print(temp.data + " ");
			temp = temp.next;
		}
	}
	// Driver program to test above
	public static void main(String[] args)
	{
		Node head = new Node(1);
		head.next = new Node(0);
		head.next.next = new Node(0);

		Node head2 = new Node(1);

		Substract ob = new Substract();
		Node result = ob.subtractLinkedList(head, head2);

		printList(result);
	}
}

Output

Linked list 1:
1 3 5 7
Linked list 2:
3 5 8
Linked list representation of difference between L1 and L2:
0 9 9 9

Time Complexity of subtract two linked lists: O(n), as no nested traversal is needed.

So, in this article, we have tried to explain the most efficient approach to subtract two numbers represented as Linked Lists. In this, we discussed the problem statement and ways to solve the problem also we discussed the approach, its algorithm, Dry run, implementation, and complexities.

FAQs

How do subtract two linked lists?

If the given linked list’s size is the same then:

Find the linked list with smaller values.
Subtract the nodes one by one of the smaller list from the larger list.
Also, keep track of the borrow while subtracting the values.

Find the sum of the two linked lists?

Traverse the linked list and calculate the size of the linked list.
Calculate the sum of the rightmost nodes of the linked list.
Also, keep track of the carry while adding the value of the linked lists.

What is a linked list?

The linked list is a set of nodes in which each node has a pointer to the next node.

Subtract Two Numbers Represented as Linked Lists