{"id":5237,"date":"2021-09-29T11:15:32","date_gmt":"2021-09-29T11:15:32","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=5237"},"modified":"2022-11-08T12:15:17","modified_gmt":"2022-11-08T12:15:17","slug":"subtract-two-numbers-represented-as-linked-lists","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/subtract-two-numbers-represented-as-linked-lists\/","title":{"rendered":"Subtract Two Numbers Represented as Linked Lists"},"content":{"rendered":"

\"\"
\nWe 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.<\/a><\/p>\n<\/p>\n

How to Subtract Two Numbers as Linked Lists<\/h2>\n

In this problem, we are given two linked lists, L1<\/strong> and L2<\/strong>. Both L1<\/strong> and L2<\/strong> 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.<\/p>\n

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.<\/p>\n

Understanding with Example<\/h3>\n

Let\u2019s try to understand this problem with the help of examples.<\/p>\n

If the list given to us be L1<\/strong> = 1 \u2192 0 \u2192 0 \u2192 NULL and L2<\/strong> = 5 \u2192 NULL.<\/p>\n

    \n
  • 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.<\/li>\n
  • 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.<\/li>\n
  • The numeric representation of list L1 is 100, and list L2 is 5. The difference between L1 and L2 is 95.<\/li>\n
  • Our output will be the linked list representation of the difference between L1 and L2, which will be 0 \u2192 9 \u2192 5 \u2192 NULL.<\/li>\n<\/ul>\n

    Let\u2019s take another example to make the problem understanding more clearer. If the given lists are L1<\/strong> = 5 \u2192 2 \u2192 3 \u2192NULL and L2<\/strong> = 6 \u2192 3 \u2192 5 \u2192 NULL.<\/p>\n

      \n
    • 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<\/strong>. <\/li>\n
    • Now our output will be the linked list representation of the difference between the numeric representation of L1 and L2, which will be 1 \u2192 1 \u2192 2 \u2192 NULL.<\/li>\n<\/ul>\n

      Some more examples<\/h3>\n

      Sample Input 1: <\/p>\n

      \"\"<\/p>\n

      Sample Output 1: <\/p>\n

      \"\"<\/p>\n

      Sample Output 2: L1<\/strong> = 1\u21922\u21925\u21926\u2192NULL, L2<\/strong> = 3\u21924\u2192NULL<\/p>\n

      Sample Output 2: 1\u21922\u21922\u21922\u2192NULL<\/p>\n

      Now, I think from the above examples, the problem statement is clear. Let\u2019s see how we can approach it.<\/p>\n

      Before moving to the approach section, try to think about how you can approach this problem.<\/p>\n

        \n
      • If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.<\/li>\n<\/ul>\n

        Let\u2019s move to the approach section.<\/p>\n

        Approach to subtract two numbers represented as linked lists<\/h2>\n

        Our approach will be simple:<\/p>\n

          \n
        • First, we have to find the greater value list among the given lists. <\/li>\n
        • How we will do that:\n
            \n
          • 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. <\/li>\n
          • 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. <\/li>\n<\/ul>\n<\/li>\n
          • After this, we will, one by one, subtract nodes of the smaller linked list from the larger list.<\/li>\n<\/ul>\n

            Let’s move to the algorithm section<\/p>\n

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

                  Dry Run for subtracting 2 numbers<\/h3>\n

                  \"\"<\/p>\n

                  \"\"<\/p>\n

                  \"\"<\/p>\n

                  \"\"<\/p>\n

                  Code Implementation to Subtract 2 Numbers Represented as Linked Lists<\/h2>\n\t\t\t\t\t\t