Add the given digit to a number stored in a linked list using recursion
Given a linked list which represents an integer number where each node is a digit of the represented integer. The task is to add a given digit N to the represented integer.
Examples:
Input: LL = 9 -> 9 -> 3 -> NULL, N = 7
Output: 1 -> 0 -> 0 -> 0 -> NULL
993 + 7 = 1000
Input: LL = 2 -> 9 -> 9 -> NULL, N = 5
Output: 3 -> 0 -> 4 -> NULL
Approach: An iterative approach to solve this problem has been discussed here. In this article, a recursive approach will be discussed.
The idea is to traverse the LinkedList recursively until the last node is reached. Once the last node has been reached, add the value of N to it. After adding, if the value is more than 9 then keep the carry and set mode (digit % 10) value to the node value and add carry to the previous stack frame node, and continue until all the stack frames are cleared from the stack.
If there is a carry after all the stack frames have been cleared then create a new node with this value which will be the new head of the linked list pointing to the previous head.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include<bits/stdc++.h>using namespace std;// Node class contains value// and next node referencestruct ListNode { int value; ListNode* next;};// To store the carryint carry = 0;void addNewValue(ListNode*, int);// Function that calls the recursive method// addNewValue to add a digit to the// number represented as the linked listListNode* addValue(ListNode* head, int addValue){ // Add the digit recursively addNewValue(head, addValue); // If there is a carry after the addition if (carry != 0) { // Create a new node ListNode* newHead = new ListNode(); // Assign it with carry newHead->value = carry; // Make it point to the head of // the linked list newHead->next = head; carry = 0; // Make it the new head return newHead; } // If there's not carry then // return the previous head else { return head; }}// Recursive function to add a digit to the number// represented as the given linked listvoid addNewValue(ListNode* head, int addValue){ // If it is the last node in the list if (head->next == NULL) { // Add the digit int val = head->value + addValue; // Find the carry if any head->value = val % 10; carry = val / 10; } else { // Preserve the current node's value and call // the recursive function for the next node int val = head->value; addNewValue(head->next, addValue); val = val + carry; head->value = val % 10; carry = val / 10; }}// Utility function to print the linked listvoid printList(ListNode* node){ while (node != NULL) { cout << node->value << " -> "; node = node->next; } cout<<"NULL";}// Driver codeint main(){ // Create the linked list 9 -> 9 -> 3 -> NULL ListNode* head = new ListNode(); head->value = 9; head->next = new ListNode(); head->next->value = 9; head->next->next = new ListNode(); head->next->next->value = 3; head->next->next->next = NULL; // Digit to be added int n = 7; head = addValue(head, n); printList(head);}// This code is contributed by rutvik_56 |
Java
// Java implementation of the approach// Node class contains value// and next node referenceclass ListNode { int value; ListNode next;}class GFG { // To store the carry private static int carry = 0; // Function that calls the recursive method // addNewValue to add a digit to the // number represented as the linked list public static ListNode addValue(ListNode head, int addValue) { // Add the digit recursively addNewValue(head, addValue); // If there is a carry after the addition if (carry != 0) { // Create a new node ListNode newHead = new ListNode(); // Assign it with carry newHead.value = carry; // Make it point to the head of // the linked list newHead.next = head; carry = 0; // Make it the new head return newHead; } // If there's not carry then // return the previous head else { return head; } } // Recursive function to add a digit to the number // represented as the given linked list private static void addNewValue(ListNode head, int addValue) { // If it is the last node in the list if (head.next == null) { // Add the digit int val = head.value + addValue; // Find the carry if any head.value = val % 10; carry = val / 10; } else { // Preserve the current node's value and call // the recursive function for the next node int val = head.value; addNewValue(head.next, addValue); val = val + carry; head.value = val % 10; carry = val / 10; } } // Utility function to print the linked list private static void printList(ListNode node) { while (node != null) { System.out.print(node.value + " -> "); node = node.next; } System.out.print("NULL"); } // Driver code public static void main(String[] args) { // Create the linked list 9 -> 9 -> 3 -> NULL ListNode head = new ListNode(); head.value = 9; head.next = new ListNode(); head.next.value = 9; head.next.next = new ListNode(); head.next.next.value = 3; head.next.next.next = null; // Digit to be added int n = 7; head = addValue(head, n); printList(head); }} |
Python
# Python implementation of the approach# Node class contains value# and next node referenceclass ListNode: def __init__(self, new_data): self.value = new_data self.next = None# To store the carrycarry = 0# Function that calls the recursive method# addNewValue to add a digit to the# number represented as the linked listdef addValue(head, addValue): global carry # Add the digit recursively addNewValue(head, addValue) # If there is a carry after the addition if (carry != 0) : # Create a node newHead = ListNode(0) # Assign it with carry newHead.value = carry # Make it point to the head of # the linked list newHead.next = head carry = 0 # Make it the head return newHead # If there's not carry then # return the previous head else : return head # Recursive function to add a digit to the number# represented as the given linked listdef addNewValue(head,addValue): global carry # If it is the last node in the list if (head.next == None) : # Add the digit val = head.value + addValue # Find the carry if any head.value = val % 10 carry = int(val / 10) else : # Preserve the current node's value and call # the recursive function for the next node val = head.value addNewValue(head.next, addValue) val = val + carry head.value = val % 10 carry = int(val / 10) # Utility function to print the linked listdef printList(node): while (node != None) : print(node.value ,end= " -> ") node = node.next print("None") # Driver code# Create the linked list 9 -> 9 -> 3 -> Nonehead = ListNode(0)head.value = 9head.next = ListNode(0)head.next.value = 9head.next.next = ListNode(0)head.next.next.value = 3head.next.next.next = None# Digit to be addedn = 7head = addValue(head, n)printList(head)# This code is contributed by Arnab Kundu |
C#
// C# implementation of the approach using System;// Node class contains value// and next node referencepublic class ListNode { public int value; public ListNode next;}class GFG{ // To store the carry private static int carry = 0; // Function that calls the recursive method // addNewValue to add a digit to the // number represented as the linked list public static ListNode addValue(ListNode head, int addValue) { // Add the digit recursively addNewValue(head, addValue); // If there is a carry after the addition if (carry != 0) { // Create a new node ListNode newHead = new ListNode(); // Assign it with carry newHead.value = carry; // Make it point to the head of // the linked list newHead.next = head; carry = 0; // Make it the new head return newHead; } // If there's not carry then // return the previous head else { return head; } } // Recursive function to add a digit to the number // represented as the given linked list private static void addNewValue(ListNode head, int addValue) { // If it is the last node in the list if (head.next == null) { // Add the digit int val = head.value + addValue; // Find the carry if any head.value = val % 10; carry = val / 10; } else { // Preserve the current node's value and call // the recursive function for the next node int val = head.value; addNewValue(head.next, addValue); val = val + carry; head.value = val % 10; carry = val / 10; } } // Utility function to print the linked list private static void printList(ListNode node) { while (node != null) { Console.Write(node.value + " -> "); node = node.next; } Console.Write("NULL"); } // Driver code public static void Main(String[] args) { // Create the linked list 9 -> 9 -> 3 -> NULL ListNode head = new ListNode(); head.value = 9; head.next = new ListNode(); head.next.value = 9; head.next.next = new ListNode(); head.next.next.value = 3; head.next.next.next = null; // Digit to be added int n = 7; head = addValue(head, n); printList(head); }}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// JavaScript implementation of the approach// Node class contains value// and next node referenceclass ListNode { constructor() { this.value = 0; this.next = null; } } // To store the carrylet carry = 0;// Function that calls the recursive method// addNewValue to add a digit to the// number represented as the linked listfunction addValue( head, addValue){ // Add the digit recursively addNewValue(head, addValue); // If there is a carry after the addition if (carry != 0) { // Create a new node var newHead = new ListNode(); // Assign it with carry newHead.value = carry; // Make it point to the head of // the linked list newHead.next = head; carry = 0; // Make it the new head return newHead; } // If there's not carry then // return the previous head else { return head; }}// Recursive function to add a digit to the number// represented as the given linked listfunction addNewValue( head, addValue){ // If it is the last node in the list if (head.next == null) { // Add the digit let val = head.value + addValue; // Find the carry if any head.value = val % 10; carry = Math.floor(val / 10); } else { // Preserve the current node's value and call // the recursive function for the next node let val = head.value; addNewValue(head.next, addValue); val = val + carry; head.value = val % 10; carry = Math.floor(val / 10); } }// Utility function to print the linked listfunction printList( node){ while (node != null) { document.write(node.value + " -> "); node = node.next; } document.write("NULL");}// Driver Code// Create the linked list 9 -> 9 -> 3 -> NULLvar head = new ListNode();head.value = 9;head.next = new ListNode();head.next.value = 9;head.next.next = new ListNode();head.next.next.value = 3;head.next.next.next = null;// Digit to be addedlet n = 7;head = addValue(head, n);printList(head); </script> |
Output:
1 -> 0 -> 0 -> 0 -> NULL
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
