Subtract two numbers represented as Linked Lists

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

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.

Problem Statement Understanding

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

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

  • 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

Code Implementation

#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: "<

						 

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: 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. This question is a must-do if you want to crack interviews of big companies. 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.

Previous post QuickSort on Singly Linked List
Next post Insertion Sort for Singly Linked List

Leave a Reply

Your email address will not be published. Required fields are marked *